本文共 3676 字，大约阅读时间需要 12 分钟。

题意

一个$01$矩阵,每次可以交换相邻的两个格子,每个格子限制了一定的交换次数

问从当前状态变到目标状态的最小操作次数,或者说明这是不可能的。

这不是水题??

有两个显而易见的事实

①.如果把所有$1$的格子复原了,那么所有$0$的格子也会复原

②.如果相邻的格子是同色的,那么不会交换,交换是没有意义的

由此我们知道,在某个$1$归位的路径上不会经过任何其他的$1$,问题转化为在图上找到一条条的路径

因为每个格子的交换次数也存在限制$val$次,我们拆点为入点和出点

源点向所有初始矩阵$1$的入点连边,流量$1$费用$0$,表示作为起点

所有终止矩阵$1$的出点向汇点连边,流量$1$费用$0$,表示作为终点

每个格子的出点向相邻格子的入点连边,流量$val$费用$1$,表示交换

每个点的入点向出点连边,流量为格子可经过次数,费用$0$

跑最小费用最大流即可有没有发现问题??

一条路径经过格子,会进入,出去,一共需要交换两次!!然而我们这样只算了一次

那还不简单??把每个格子经过次数直接除以二不就行了…

错了,因为如果把这个格子作为起点或终点,就只需要交换一次。

所以一个可行的解决方案是,反正起点和终点是一定需要经过的,我们可以预先扣除这些流量

也就是对于起点和终点,入点向出点连流量为$(c[i][j]-1)/2+1$的费用$0$的边即可

#include 
   
    using namespace std;const int maxn = 3e5+10;const int inf = 1e9;struct edge{
       int to,nxt,flow,w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int flow,int w){
       d[++cnt] = ( edge ){
   v,head[u],flow,w},head[u] = cnt;    d[++cnt] = ( edge ){
   u,head[v],0,-w},head[v] = cnt;}int dis[maxn],flow[maxn],pre[maxn],vis[maxn],n,m,s,t,res1,res2;char a[100][100],b[100][100],c[100][100];bool spfa(int s,int t,int mx)//最小费用最大流{
       queue
    
     q;    for(int i=0;i<=mx;i++)  dis[i] = inf, vis[i] = 0;    dis[s] = 0; flow[s] = inf; q.push(s);    while( !q.empty() )    {
           int u = q.front(); q.pop();        vis[u] = 0;        for(int i=head[u];i;i=d[i].nxt )        {
               int v = d[i].to;            if( dis[v]>dis[u]+d[i].w && d[i].flow )            {
                   dis[v] = dis[u]+d[i].w; flow[v] = min( flow[u],d[i].flow ); pre[v] = i;                if( !vis[v] )   vis[v] = 1, q.push(v);            }        }    }    return dis[t]!=inf;}int MCMF(int s,int t,int mx){
       int mincost = 0,maxflow = 0;    while( spfa(s,t,mx) )    {
           int i,x = t;        maxflow += flow[t]; mincost += flow[t]*dis[t];        while( x!=s )        {
               i = pre[x];            d[i].flow -= flow[t], d[i^1].flow += flow[t];            x = d[i^1].to;        }    }    if( maxflow!=res1 )  return -1;    return mincost;}int fx[10] = {
   0,0,1,1,1,-1,-1,-1},fy[10] = {
   -1,1,-1,0,1,-1,0,1};int id(int x,int y){
    return (x-1)*m+y; }int main(){
       cin >> n >> m;    for(int i=1;i<=n;i++)   cin >> ( a[i]+1 );    for(int i=1;i<=n;i++)   cin >> ( b[i]+1 );    for(int i=1;i<=n;i++)   cin >> ( c[i]+1 );    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)        if( a[i][j]==b[i][j] )  a[i][j] = b[i][j] = '0';//都是终点,当作没有棋子    s = 0, t = n*m*2+1;    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)    {
           int val = c[i][j]-'0';        if( a[i][j]=='1' )//起点        {
               res1++;            add( id(i,j),id(i,j)+n*m,( val-1 )/2+1,0 );            add( s,id(i,j),1,0);        }        else if( b[i][j]=='1' )//终点        {
               res2++;            add( id(i,j),id(i,j)+n*m,( val-1 )/2+1,0 );            add( id(i,j)+n*m,t,1,0 );        }        else//啥都不是            add( id(i,j),id(i,j)+n*m,val/2,0 );        for(int w=0;w<=7;w++)        {
               int nx = i+fx[w], ny = j+fy[w];            if( nx<1 || nx>n || ny <1 || ny >m )    continue;            add( id(i,j)+n*m,id(nx,ny),inf,1 );        }    }    if( res1 != res2 ){
    cout << -1; return 0; }    cout << MCMF(s,t,t);}
    
   

然后又有巨巨发明了另外巧妙的建图方式

因为一个点交换的方式无非是进去,出来两种

所以把一个点拆分为三个点,分别是$in,mid,out$

如果一个格子是起点,源点连向$mid$流量$1$费用$0$的边

如果一个格子是终点,从$mid$向汇点连流量$1$费用$0$的边

这样满足起点和终点只会花费$1$次交换

$in$向$mid$连流量为格子容量一半费用$0$的边,$mid$向$out$连流量为格子容量一半费用$0$的边

但是容量为奇数的不是均分的,多出的一点流量,如果是起点分给$mid-out$,是终点分给$in-mid$

比较好理解。

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115375897 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！