[CQOI2012] 交换棋子

题意

有一个 n 行 m 列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第 i 行第 j 列的格子只能参与 次交换。

求最小交换总次数。如果无解,输出 -1。

分析

非常令人发指的网络流

要从起始状态转移到目标状态,相当于在移动黑棋

那么把黑棋当做 1 个单位的流,于是我们需要构建一个网络图推送流到汇点

我们定义一下起点和终点:

  • 起点:起始状态为黑棋,目标状态为白棋的点
  • 终点:起始状态为白棋,目标状态为黑棋的点

显然源点连起点,终点连汇点,容量为 1

我们考虑移动一枚黑棋的路径 .

除了 经历 1 次交换, 都经历 2 次交换.

把二元组 映射成整数 .

交换次数是针对点而言,因此拆点 为边,两端为 容量为交换次数上限的一半

那么在这条边增加 1 单位流的含义就是它参与了 2 次交换

相邻结点 就连接 ,容量为 INF.

上述方法没有考虑起点和终点的情况:

  • 源点连起点,从源点向这里推送 1 单位的流(表示起点经历 2 次交换)。
  • 终点连汇点,从这里向汇点推送 1 单位的流(表示终点经历 2 次交换)。

那么怎么体现起点、终点只经历 1 次交换呢?

既然不能改变流,就增加容量吧

把起点、终点的边的容量加 1 单位,这就等价于起点终点只经历 1 次交换

完成了网络图的构建,那么最小交换次数呢?

给相邻结点的边加 1 单位费用即可。

综上,建模如下:

  • 二元组 映射为整数 .
  • 拆点 变成 建边 .
  • 特别地,如果 是起点或终点, .
  • 对于与 相邻的结点 ,建边 .
  • 源点连起点,容量为 1,费用为 0
  • 终点为汇点,容量为 1,费用为 0

跑最小费用最大流即可

矩阵建模一定小心!!!!!——本蒟蒻太菜的证明之感言

代码

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e4,M=2e6,INF=0x3f3f3f3f;
int n,m,s,t;

struct qxx{int nex,t,v,c;};
qxx e[M];
int h[N],cnt=1;
void add_path(int f,int t,int v,int c){e[++cnt]=(qxx){h[f],t,v,c},h[f]=cnt;}
void add_flow(int f,int t,int v,int c){add_path(f,t,v,c),add_path(t,f,0,-c);}

int dis[N],pre[N],incf[N];
bool vis[N];
bool spfa(){memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(s),dis[s]=0,incf[s]=INF,incf[t]=0;
    while(q.size()){int u=q.front();q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v,&c=e[i].c;
            if(!w||dis[v]<=dis[u]+c)continue;
            dis[v]=dis[u]+c,incf[v]=min(incf[u],w),pre[v]=i;
            if(!vis[v])q.push(v),vis[v]=1;
        }
    }
    return incf[t];
}
int maxflow,mincost;
void update(){maxflow+=incf[t];
    for(int u=t;u!=s;u=e[pre[u]^1].t){e[pre[u]].v-=incf[t],e[pre[u]^1].v+=incf[t];
        mincost+=e[pre[u]].c*incf[t];
    }
}
char str[3][30][30];
int count1,count2;
int main(){scanf("%d%d",&n,&m);
    s=0,t=m*n*2+10;
    for(int i=1;i<=n;i++)scanf("%s",str[0][i]+1);
    for(int i=1;i<=n;i++)scanf("%s",str[1][i]+1);
    for(int i=1;i<=n;i++)scanf("%s",str[2][i]+1);
    for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int u=(i-1)*m+j,x=str[2][i][j]-'0';
            if(str[0][i][j]=='0'&&str[1][i][j]=='0')add_flow(u<<1,u<<1|1,x>>1,0);
            else if(str[0][i][j]=='1'&&str[1][i][j]=='0')add_flow(u<<1,u<<1|1,(x+1)>>1,0),add_flow(s,u<<1,1,0),count1++;
            else if(str[0][i][j]=='0'&&str[1][i][j]=='1')add_flow(u<<1,u<<1|1,(x+1)>>1,0),add_flow(u<<1|1,t,1,0),count2++;
            else add_flow(u<<1,u<<1|1,x>>1,0);
            if(i>1)add_flow(u<<1|1,(u-m)<<1,INF,1);
            if(i<n)add_flow(u<<1|1,(u+m)<<1,INF,1);
            if(j>1)add_flow(u<<1|1,(u-1)<<1,INF,1);
            if(j<m)add_flow(u<<1|1,(u+1)<<1,INF,1);
            if(i>1&&j>1)add_flow(u<<1|1,(u-m-1)<<1,INF,1);
            if(i>1&&j<m)add_flow(u<<1|1,(u-m+1)<<1,INF,1);
            if(i<n&&j<m)add_flow(u<<1|1,(u+m+1)<<1,INF,1);
            if(i<n&&j>1)add_flow(u<<1|1,(u+m-1)<<1,INF,1);
        }
    }
    if(count1!=count2)return puts("-1"),0;
    while(spfa())update();
    if(maxflow!=count1)return puts("-1"),0;
    printf("%d",mincost);
    return 0;
}

  转载请注明: Sshwy's Blog [CQOI2012] 交换棋子

 上一篇
[ZJOI2010] 网络扩容 [ZJOI2010] 网络扩容
题意给定一张有向图,每条边都有容量 和扩容费用 。这里扩容费用指将容量扩大 1 所需的费用。求: 在不扩容的情况下,1 到 N 的最大流. 将 1 到 N 的最大流增加 K 所需的最小扩容费用. Subtask1
2019.01.14
下一篇 
[SDOI2009] 晨跑 [SDOI2009] 晨跑
题意在加权有向图中求一路径集合 满足 起点为 ,终点为 ,即 . 集合内的路径除了起点终
2019.01.12
  目录