bzoj
luogu
sol
因為交換兩個同色的棋子是沒有意義的，是以可以視作隻有黑色的棋子在棋盤上，每次向相鄰的格子移動一步，求最小移動次數。
把每個格子拆成三個點：原點，出點，入點。
考慮一個格子，有且僅有四種情況：初始沒有棋子目标也沒有棋子，初始沒有棋子目标有棋子，初始有棋子目标沒有棋子，初始有棋子目标也有棋子。
發現第一種和第四種其實是一樣的，是以就隻有三種情況了。
初始沒有棋子目标也沒有棋子
棋子數量守恒，即棋子進入這個格子的次數同等于出去的次數。顯然這個次數都不能超過\(\lfloor\frac{c}{2}\rfloor\)，是以原點向出點連\(\lfloor\frac{c}{2}\rfloor\)的邊，入點向原點連\(\lfloor\frac{c}{2}\rfloor\)的邊。
初始狀态沒有棋子目标有棋子
棋子數量+1，也就是說棋子進入這個格子的次數比出去的次數多1。那麼出去的限制次數就是\(\lfloor\frac{c-1}{2}\rfloor\)，進入的限制次數為\(\lfloor\frac{c+1}{2}\rfloor\)。原點向出點連\(\lfloor\frac{c+1}{2}\rfloor\)的邊，入點向原點連\(\lfloor\frac{c-1}{2}\rfloor\)的邊，同時從源點\(S\)向原點連\(1\)的邊。
初始狀态有棋子目标沒有棋子
同上理，棋子數量-1，也就是說棋子進入這個格子的次數比出去的次數少1。出去的限制次數\(\lfloor\frac{c+1}{2}\rfloor\)，進入的限制次數\(\lfloor\frac{c-1}{2}\rfloor\)。原點向出點連\(\lfloor\frac{c-1}{2}\rfloor\)的邊，入點向原點連\(\lfloor\frac{c+1}{2}\rfloor\)的邊，同時從原點向彙點\(T\)連\(1\)的邊。
然後相鄰的格子，從出點連向入點，容量\(inf\)費用為\(1\)。
注意這題是八聯通！
code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 80;
const int inf = 1e9;
struct edge{int to,nxt,w,cost;}a[N*N*N];
int n,m,p[N][N],tot,s,t,head[N*N],cnt=1,dis[N*N],vis[N*N],pe[N*N],maxflow,flow,ans;
char st[N][N],ed[N][N],ch[N][N];
queue<int>Q;
void link(int u,int v,int w,int cost)
{
a[++cnt]=(edge){v,head[u],w,cost};
head[u]=cnt;
a[++cnt]=(edge){u,head[v],0,-cost};
head[v]=cnt;
}
bool spfa()
{
memset(dis,63,sizeof(dis));
dis[s]=0;Q.push(s);
while (!Q.empty())
{
int u=Q.front();Q.pop();
for (int e=head[u];e;e=a[e].nxt)
{
int v=a[e].to;
if (a[e].w&&dis[v]>dis[u]+a[e].cost)
{
dis[v]=dis[u]+a[e].cost;pe[v]=e;
if (!vis[v]) vis[v]=1,Q.push(v);
}
}
vis[u]=0;
}
if (dis[t]==dis[0]) return false;
int sum=inf;
for (int i=t;i!=s;i=a[pe[i]^1].to)
sum=min(sum,a[pe[i]].w);
flow+=sum;ans+=sum*dis[t];
for (int i=t;i!=s;i=a[pe[i]^1].to)
a[pe[i]].w-=sum,a[pe[i]^1].w+=sum;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i) scanf("%s",st[i]+1);
for (int i=1;i<=n;++i) scanf("%s",ed[i]+1);
for (int i=1;i<=n;++i) scanf("%s",ch[i]+1);
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
p[i][j]=++tot,ch[i][j]-='0';
s=3*tot+1;t=s+1;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (st[i][j]==ed[i][j])
{
link(p[i][j],p[i][j]+tot,ch[i][j]/2,0);
link(p[i][j]+tot+tot,p[i][j],ch[i][j]/2,0);
}
else if (st[i][j]=='1'&&ed[i][j]=='0')
{
link(s,p[i][j],1,0);++maxflow;
link(p[i][j],p[i][j]+tot,(ch[i][j]+1)/2,0);
link(p[i][j]+tot+tot,p[i][j],(ch[i][j]-1)/2,0);
}
else
{
link(p[i][j],t,1,0);
link(p[i][j],p[i][j]+tot,(ch[i][j]-1)/2,0);
link(p[i][j]+tot+tot,p[i][j],(ch[i][j]+1)/2,0);
}
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
{
if (i>1) link(p[i][j]+tot,p[i-1][j]+tot+tot,inf,1);
if (j>1) link(p[i][j]+tot,p[i][j-1]+tot+tot,inf,1);
if (i<n) link(p[i][j]+tot,p[i+1][j]+tot+tot,inf,1);
if (j<m) link(p[i][j]+tot,p[i][j+1]+tot+tot,inf,1);
if (i>1&&j>1) link(p[i][j]+tot,p[i-1][j-1]+tot+tot,inf,1);
if (i>1&&j<m) link(p[i][j]+tot,p[i-1][j+1]+tot+tot,inf,1);
if (i<n&&j>1) link(p[i][j]+tot,p[i+1][j-1]+tot+tot,inf,1);
if (i<n&&j<m) link(p[i][j]+tot,p[i+1][j+1]+tot+tot,inf,1);
}
while (spfa()) ;
printf("%d\n",flow==maxflow?ans:-1);
return 0;
} 轉載于:https://www.cnblogs.com/zhoushuyu/p/8613165.html