网络流/费用流

　　跪跪跪，居然还可以这样建图……

　　题解：http://www.cnblogs.com/zig-zag/archive/2013/04/21/3033485.html

考虑每个点的交换限制的约束，一看就知道是点容量，但是这里不是一分为二，而是一分为三。

首先我们把问题化简，变成对于原图上所有黑点，找到一个新图中的黑点，进行多次交换后到达。我们看到多次交换实际上是走了一条路径(这里不是最短路)。对于这条路径的起点和终点，仅进行了1次交换，而路径上的其他点都交换了2次。所以我们需要构造一种图来把这个交换次数的差异体现出来，于是：

对于每个点一分为三，分为p0,p1,p2，对于每个点，如果它是原图中得黑点，连边<p1,p0,c/2,0>，<p0,p2,(c+1)/2>，<st,p0,1,0>；如果它是新图中得黑点，连边<p1,p0,(c+1)/2>，<p0,p2,c/2,0>，<p0,ed,1,0>；如果它在两个图中都是白点，那么连边<p1,p0,c/2,0>，<p0,p2,c/2,0>。这样就可以体现出点容量的差异了。

然后对于原图中可以交换的两个点(i,j)连接<pi2,pj1,inf,1>，那么这种边每流过1的流量就意味着(i,j)交换了一次，那么费用就是最终的答案了。

 /**************************************************************

     Problem: 2668

     User: Tunix

     Language: C++

     Result: Accepted

     Time:24 ms

     Memory:48464 kb

 ****************************************************************/

 //BZOJ 2668

 #include<cmath>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 inline int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 const int N=,M=,INF=~0u>>;

 typedef long long LL;

 /******************tamplate*********************/

 char s1[][],s2[][],s3[][];

 int n,m,a[][],b[][],c[][],num[][],b1,b2,ans,flow,tot;

 inline int gcd(int a,int b){return b ? gcd(b,a%b) : a;}

 bool judge(int x,int y){

     int q=x*x-y*y,s=sqrt(q);

     if (s*s==q && gcd(y,s)==) return ;

     return ;

 }

 struct edge{int from,to,v,c;};

 struct Net{

     edge E[M];

     int head[N],next[M],cnt;

     void ins(int x,int y,int z,int c){

         E[++cnt]=(edge){x,y,z,c};

         next[cnt]=head[x]; head[x]=cnt;

     }

     void add(int x,int y,int z,int c){

         ins(x,y,z,c); ins(y,x,,-c);

     }

     int from[N],Q[M],d[N],S,T;

     bool inq[N];

     bool spfa(){

         int l=,r=-;

         F(i,,T) d[i]=INF;

         d[S]=; Q[++r]=S; inq[S]=;

         while(l<=r){

             int x=Q[l++];

             inq[x]=;

             for(int i=head[x];i;i=next[i])

                 if(E[i].v> && d[x]+E[i].c<d[E[i].to]){

                     d[E[i].to]=d[x]+E[i].c;

                     from[E[i].to]=i;

                     if (!inq[E[i].to]){

                         Q[++r]=E[i].to;

                         inq[E[i].to]=;

                     }

                 }

         }

         return d[T]!=INF;

     }

     void mcf(){

         int x=INF,y,z;

         for(int i=from[T];i;i=from[E[i].from])

             x=min(x,E[i].v);

         for(int i=from[T];i;i=from[E[i].from]){

             E[i].v-=x;

             E[i^].v+=x;

         }

         flow+=x;

         ans+=x*d[T];

     }

     void init(){

         n=getint(); m=getint(); cnt=;

         tot=n*m; S=; T=tot*+;

         F(i,,n) scanf("%s",s1[i]+);

         F(i,,n) scanf("%s",s2[i]+);

         F(i,,n) scanf("%s",s3[i]+);

         F(i,,n) F(j,,m){

             a[i][j]=s1[i][j]-''; if(a[i][j]) b1++;

             b[i][j]=s2[i][j]-''; if(b[i][j]) b2++;

             c[i][j]=s3[i][j]-'';

             if (a[i][j]&&b[i][j]) a[i][j]=b[i][j]=,b1--,b2--;

         }

         F(i,,n) F(j,,m){

             int now=(i-)*m+j;

             num[i][j]=now;

             if (a[i][j]){

                 add(S,now,,);

                 add(tot+now,now,c[i][j]/,);

                 add(now,*tot+now,(c[i][j]+)/,);

             }else if(b[i][j]){

                 add(now,T,,);

                 add(tot+now,now,(c[i][j]+)/,);

                 add(now,*tot+now,c[i][j]/,);

             }else{

                 add(tot+now,now,c[i][j]/,);

                 add(now,*tot+now,c[i][j]/,);

             }

         }

         F(i,,n) F(j,,m){

             if (i>) add(*tot+num[i][j],tot+num[i-][j],INF,);

             if (j>) add(*tot+num[i][j],tot+num[i][j-],INF,);

             if (i<n) add(*tot+num[i][j],tot+num[i+][j],INF,);

             if (j<m) add(*tot+num[i][j],tot+num[i][j+],INF,);

             if (i> && j>) add(*tot+num[i][j],tot+num[i-][j-],INF,);

             if (i<n && j<m) add(*tot+num[i][j],tot+num[i+][j+],INF,);

             if (i> && j<m) add(*tot+num[i][j],tot+num[i-][j+],INF,);

             if (i<n && j>) add(*tot+num[i][j],tot+num[i+][j-],INF,);

         }

         if (b1==b2){

             while(spfa()) mcf();

             if (flow!=b1) ans=-;

         }else ans=-;

         printf("%d\n",ans);

     }

 }G1;

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("input.txt","r",stdin);

 //  freopen("2668.out","w",stdout);

 #endif

     G1.init();

     return ;

 }

巴特西

【BZOJ】【2668】【CQOI2012】交换棋子

网络流/费用流

最新文章

热门文章