bzoj4873: [Shoi2017]寿司餐厅（最小割）

大佬们是怎么一眼看出这是一个最大权闭合子图的……大佬好强->这里

1.把所有区间$(i,j)$看成一个点，如果权值大于0，则从$S$向他连边，容量为权值，否则从它向$T$连边，容量为权值的相反数

2.对于区间$(i,j)$，向所有的寿司$i$到$j$连边，表示选这个区间这些寿司必须选

3.对每一个寿司类型$w[i]$，为他们各自开一个点，向$T$连边，容量为$m*w[i]*w[i]$

4.对每一个寿司向他们所属的类型$w[i]$连边，容量为$inf$，向$T$连边，容量为$w[i]$

5.对于所有区间$(i,j)$，向区间$(i-1,j),(i,j-1)$连边，容量$inf$，表示选了大的必须选小的

然后用总收益减去最小割就行了

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #define inf 0x3f3f3f3f

 #define ll long long

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=,M=;

 int head[N],Next[M],ver[M],edge[M],tot=;

 int dep[N],cur[N],S,T;

 queue<int> q;

 inline void add(int u,int v,int e){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;

     ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=;

 }

 bool bfs(){

     while(!q.empty()) q.pop();

     for(int i=S;i<=T;++i) cur[i]=head[i];

     memset(dep,-,sizeof(dep));

     q.push(S),dep[S]=;

     while(!q.empty()){

         int u=q.front();q.pop();

         for(int i=head[u];i;i=Next[i]){

             int v=ver[i];

             if(dep[v]<&&edge[i]){

                 dep[v]=dep[u]+,q.push(v);

                 if(v==T) return true;

             }

         }

     }

     return false;

 }

 int dfs(int u,int limit){

     if(u==T||!limit) return limit;

     int flow=,f;

     for(int i=cur[u];i;i=cur[u]=Next[i]){

         int v=ver[i];

         if(dep[v]==dep[u]+&&(f=dfs(v,min(limit,edge[i])))){

             flow+=f,limit-=f;

             edge[i]-=f,edge[i^]+=f;

             if(!limit) break;

         }

     }

     if(!flow) dep[u]=-;

     return flow;

 }

 int dinic(){

     int flow=;

     while(bfs()) flow+=dfs(S,inf);

     return flow;

 }

 int n,m,a[],mp[][],id[][],cnt=;

 int idw[];bool vis[];ll sum=;

 void build(){

     S=;

     for(int i=;i<=n;++i)

     for(int j=;j<=n;++j)

     id[i][j]=++cnt;

     for(int i=;i<=n;++i)

     if(!vis[a[i]]) vis[a[i]]=,idw[a[i]]=++cnt;

     T=cnt+n+;

     memset(vis,,sizeof(vis));

     for(int i=;i<=n;++i)

     if(!vis[a[i]]) vis[a[i]]=,add(idw[a[i]],T,m*a[i]*a[i]);

     for(int i=;i<=n;++i)

     add(i+cnt,idw[a[i]],inf),add(i+cnt,T,a[i]);

     for(int i=;i<=n;++i)

     for(int j=i;j<=n;++j){

         if(mp[i][j]>){

             sum+=mp[i][j];

             add(S,id[i][j],mp[i][j]);

             add(id[i][j],i+cnt,inf);

             add(id[i][j],j+cnt,inf);

         }

         else if(mp[i][j]<){

             add(id[i][j],T,-mp[i][j]);

             add(id[i][j],i+cnt,inf);

             add(id[i][j],j+cnt,inf);

         }

         if(i!=j){

             add(id[i][j],id[i+][j],inf);

             add(id[i][j],id[i][j-],inf);

         }

     }

 }

 int main(){

     //freopen("testdata.in","r",stdin);

     n=read(),m=read();

     for(int i=;i<=n;++i) a[i]=read();

     for(int i=;i<=n;++i)

     for(int j=i;j<=n;++j)

     mp[i][j]=read();

     build();

     printf("%lld\n",sum-dinic());

     return ;

 }

巴特西

bzoj4873: [Shoi2017]寿司餐厅（最小割）

最新文章

热门文章