首页 > 代码库 > NSOJ A fairy tale of the two（最小费用最大流、SPFA版本、ZKW版本）
NSOJ A fairy tale of the two（最小费用最大流、SPFA版本、ZKW版本）
n，m<=20，给两个n×m布尔矩阵，每次操作可将第一个矩阵的2个相邻元素互换。输出最少操作次数使得两个矩阵完全一样。
比赛的时候想过按照二分图完美匹配的类似做法构图，不过想到边太多以及卡各种题卡得没脾气，就先放放等赛后搞了。。。
看题解发现有更好的构图，所以就算当时搞了也是TLE。。。。
先对所有格子及其上下左右连条流量为inf，费用为1的边，表示使用这条边每次是花费1个操作。
然后将第一个矩阵为1的点连S，流量为1，费用0，表示这个1可以用于满足第二个矩阵的某一个需要
第二个矩阵为1的点连T，流量为1，费用0，表示满足了这个1的需求
答案就是满流的最小费用了。。
以前都是用SPFA版本的，第一次用ZKW版本。。。
参考：
ZKW： http://www.artofproblemsolving.com/blog/54262
DMute：http://blog.sina.com.cn/s/blog_76f6777d0101bbc8.html
这里算是把ZKW封装模板化，备用。。。
SPFA版本：1884ms
ZKW版本：276ms
ZKW使用的是选d[v]==d[u]+w(u,v)的思想
SPFA版本：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <queue>using namespace std;#define ll long long#define maxn 444#define maxe 55000#define inf 0x3f3f3f3fstruct Edge{ int u, v, nxt, cap, cost;}edge[maxe];int head[maxn];struct MinCostMaxFlow{ queue<int> que; int add; // edges number int vn; // total vertex number int cost[maxn], in[maxn], pre[maxn]; bool vis[maxn]; void init(int sz){ add = 0; vn = sz + 10; memset(head, -1, sizeof(head)); while (!que.empty()) que.pop(); } void insert(int u, int v, int w, int c){// u, v, capacity, cost edge[add].u = u; edge[add].v = v; edge[add].cap = w; edge[add].cost = c; edge[add].nxt = head[u]; head[u] = add++; edge[add].u = v; edge[add].v = u; edge[add].cap = 0; edge[add].cost = -c; edge[add].nxt = head[v]; head[v] = add++; } bool spfa(int s, int e){ memset(cost, 0x3f3f3f3f, sizeof(cost)); memset(in, 0, sizeof(in)); memset(vis, 0, sizeof(vis)); cost[s] = 0; pre[s] = -1; que.push(s); vis[s] = true; in[s]++; while (!que.empty()){ int u = que.front(); que.pop(); vis[u] = false; for (int i = head[u]; i != -1; i = edge[i].nxt){ int v = edge[i].v; if (edge[i].cap > 0 && cost[v] > cost[u] + edge[i].cost){ cost[v] = cost[u] + edge[i].cost; pre[v] = i; if (!vis[v]){ que.push(v); vis[v] = true; in[v]++; if (in[v] > vn) return false; } } } } return cost[e] < inf; } void mincostmaxflow(int s, int e, int &mincost, int &maxflow){ mincost = 0, maxflow = 0; while (spfa(s, e)){ int flow = inf; for (int i = pre[e]; i != -1; i = pre[edge[i].u]){ flow = min(flow, edge[i].cap); } maxflow += flow; for (int i = pre[e]; i != -1; i = pre[edge[i].u]){ edge[i].cap -= flow; edge[i ^ 1].cap += flow; } mincost += cost[e] * flow; } }}net;int a[22][22];int b[22][22];int dx[]={0,1,0,-1};int dy[]={1,0,-1,0};int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",a[i]+j); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",b[i]+j); net.init(n*m+2); for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ for(int k=0;k<4;++k){ int ii=i+dx[k], jj=j+dy[k]; int u=(i-1)*m+j, v=(ii-1)*m+jj; if(ii&&jj&&ii<=n&&jj<=m) net.insert(u,v,inf,1); } if(a[i][j]) net.insert(0,(i-1)*m+j,1,0); if(b[i][j]) net.insert((i-1)*m+j,n*m+1,1,0); } } int ans1=-1,ans2=-1; net.mincostmaxflow(0,n*m+1,ans1,ans2); printf("%d\n",ans1); } return 0;}
ZKW：
#include <cstdio>#include <cstring>#include <iostream>using namespace std;#define maxn 410#define maxm 510000#define inf 0x3f3f3f3fstruct Edge{ int u,v,nxt,cap,cost;}edge[maxm];int head[maxn];struct ZKW_CostFlow{// 1-based int S,T; int add;// edges number bool vis[maxn]; int dis[maxn], slk[maxn]; int ans; void init(){ add=0; memset(head, -1, sizeof(head)); } void insert(int u, int v, int w, int c){// u, v, capacity, cost edge[add].u = u; edge[add].v = v; edge[add].cap = w; edge[add].cost = c; edge[add].nxt = head[u]; head[u] = add++; edge[add].u = v; edge[add].v = u; edge[add].cap = 0; edge[add].cost = -c; edge[add].nxt = head[v]; head[v] = add++; } int aug(int u,int f){ int left=f; if(u==T){ans+=f*dis[S];return f;} vis[u]=true; for(int i=head[u];i!=-1;i=edge[i].nxt){ int cap = edge[i].cap, v = edge[i].v; if(cap>0 && vis[v]==false){ int t = dis[v] + edge[i].cost - dis[u]; if(t==0){ int delt = aug(v, cap<left?cap : left); if(delt>0) edge[i].cap-=delt, edge[i^1].cap+=delt, left-=delt; if(left==0) return f; }else slk[v] = t<slk[v]?t:slk[v]; } } return f-left; } bool modlabel(int n){ int delt = inf; for(int i=1;i<=n;++i) if(!vis[i]) delt=min(delt,slk[i]), slk[i]=inf; if(delt==inf) return true; for(int i=1;i<=n;++i) if(vis[i]) dis[i]+=delt; return false; } void ZKW_Flow(int src,int des,int n,int& micost,int& maflow){ S=src, T=des; ans=micost=maflow=0; memset(dis,0,sizeof(dis)); memset(slk,0x3f,sizeof(slk)); do{ int tmp=0; do{ memset(vis,false,sizeof(vis)); maflow+=tmp; }while(tmp=aug(S,inf)); }while(!modlabel(n)); micost=ans; }}net;// 1-basedint a[22][22];int b[22][22];int dx[]={0,1,0,-1};int dy[]={1,0,-1,0};int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",a[i]+j); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",b[i]+j); net.init(); for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ for(int k=0;k<4;++k){ int ii=i+dx[k], jj=j+dy[k]; int u=(i-1)*m+j, v=(ii-1)*m+jj; if(ii&&jj&&ii<=n&&jj<=m) net.insert(u,v,inf,1); } if(a[i][j]) net.insert(n*m+1,(i-1)*m+j,1,0); if(b[i][j]) net.insert((i-1)*m+j,n*m+2,1,0); } } int ans1=-1,ans2=-1; net.ZKW_Flow(n*m+1,n*m+2,n*m+2,ans1,ans2); printf("%d\n",ans1); } return 0;}
NSOJ A fairy tale of the two（最小费用最大流、SPFA版本、ZKW版本）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。