洛谷P3159 [CQOI2012]交换棋子

巧妙的拆点方式，首先把1看成黑点，0看成空的，几次交换就可以看成一条路径

1）从容量上看，这条路径为1-2-2-2-2-2-……-2-1

2）从费用上看，这条路径每条边费用都是1

于是用一种巧妙的拆点方式，把一个点拆成三个，连两条边，成为一条链，

然后如果是黑点的话就由s向中间那个点连边，如果是路过的话就由一条链的尾部向另一条链的首部连边

这样就满足了上面的条件1）2)

容量的话如果是黑点出来就是(c+1)/2，进来是c/2，其他的以此类推

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<queue>

 #define rint register int

 #define ll long long

 #define MAXN 2000+10

 #define pb push_back

 #define INF 0x7f7f7f7f

 #define oo 0x7f7f7f7f7f7f7f7f

 #define pil pair<int,ll>

 #define mp make_pair

 using namespace std;

 int read(){

     int x=,f=;char ch=getchar();

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

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

     return x*f;

 }

 struct E{

     int from,to,cap,flow;

     ll cost;

     E(int x=,int y=,int c=,int f=,ll w=0LL){

         from=x,to=y,cap=c,flow=f,cost=w;

     }

 };

 struct Dinic{

     int n,m,s,t;

     vector<E> es;

     vector<int> G[MAXN];

     void init(int n,int s,int t){

         this->n=n;

         this->s=s,this->t=t;

         es.clear();

         for(int i=;i<=n;i++)G[i].clear();

     }

     void add(int x,int y,int cap,ll cost){

         es.pb(E(x,y,cap,,cost));

         es.pb(E(y,x,,,-cost));

         m=es.size();

         G[x].pb(m-),G[y].pb(m-);

     }

     int p[MAXN],a[MAXN];

     ll d[MAXN];

     int b[MAXN];

     bool SPFA(int &flow,ll &cost){

         p[s]=,a[s]=INF;

         memset(d,0x7f,sizeof(d));

         d[s]=;

         memset(b,,sizeof(b));

         b[s]=;

         queue<int> q;

         q.push(s);

         while(!q.empty()){

             int x=q.front();q.pop();b[x]=;

             for(rint i=;i<G[x].size();i++){

                 E &e=es[G[x][i]];

                 if(e.cap>e.flow&&d[e.to]>d[x]+e.cost){

                     p[e.to]=G[x][i];

                     a[e.to]=min(a[x],e.cap-e.flow);

                     d[e.to]=d[x]+e.cost;

                     if(!b[e.to]){

                         b[e.to]=;

                         q.push(e.to);

                     }

                 }

             }

         }

         if(oo==d[t]){

             return ;

         }

         flow+=a[t];

         cost+=a[t]*d[t];

         for(rint i=t;i!=s;i=es[p[i]].from){

             es[p[i]].flow+=a[t];

             es[p[i]^].flow-=a[t];

         }

         return ;

     }

     pil MaxfMinc(){

         int flow=;

         ll cost=0LL;

         while(SPFA(flow,cost));

         return mp(flow,cost);

     }

 }D;

 int n,m,s=,t=MAXN-;

 int id[][][];

 int a[][],b[][],p[][];

 int cnt1=,cnt2=;

 void init(){

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

     D.init(t,s,t);

     char c[];

     for(rint i=;i<=n;i++){

         for(rint j=;j<=m;j++){

             id[][i][j]=(i-)*m+j;

         }

     }

     for(rint k=;k<=;k++){

         for(rint i=;i<=n;i++){

             for(rint j=;j<=m;j++){

                 id[k][i][j]=id[k-][i][j]+n*m;

             }

         }

     }

     for(rint i=;i<=n;i++){

         scanf("%s",c+);

         for(rint j=;j<=m;j++){

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

         }

     }

     for(rint i=;i<=n;i++){

         scanf("%s",c+);

         for(rint j=;j<=m;j++){

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

         }

     }

     for(rint i=;i<=n;i++){

         for(rint j=;j<=m;j++){

             if(a[i][j]&&b[i][j]){

                 a[i][j]=b[i][j]=;

             }

             else if(a[i][j]){

                 cnt1++;

             }

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

                 cnt2++;

             }

         }

     }

     for(rint i=;i<=n;i++){

         scanf("%s",c+);

         for(rint j=;j<=m;j++){

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

         }

     }

 }

 void add(int x,int y,int c1,int c2){

     D.add(id[][x][y],id[][x][y],c1,);

     D.add(id[][x][y],id[][x][y],c2,);

 }

 void solve(){

     int dx[]={,,-,,-,-,,};

     int dy[]={,-,,,-,,-,};

     for(rint i=;i<=n;i++){

         for(rint j=;j<=m;j++){

             if(a[i][j]){

                 add(i,j,p[i][j]>>,(p[i][j]+)>>);

                 D.add(s,id[][i][j],,);

             }

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

                 add(i,j,(p[i][j]+)>>,p[i][j]>>);

                 D.add(id[][i][j],t,,);

             }

             else{

                 add(i,j,(p[i][j]+)>>,p[i][j]>>);

             }

             for(rint k=;k<;k++){

                 int x=i+dx[k],y=j+dy[k];

                 if(<=x&&x<=n&&<=y&&y<=m){

                     D.add(id[][i][j],id[][x][y],INF,);

                 }

             }

         }

     }

     pil ans=D.MaxfMinc();

     if(ans.first!=cnt1||cnt1!=cnt2){

         printf("-1\n");

     }

     else{

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

     }

 }

 int main()

 {

     init();

     solve();

     return ;

 }

巴特西

洛谷P3159 [CQOI2012]交换棋子

最新文章

热门文章