Number Link

说是神仙题也不为过

好吧我承认我只是单纯的菜

其实这题的建模真的那么难想吗?恐怕没有

这题的实质还是路径覆盖,覆盖每个点且代价最小

$Ⅰ.如何处理奇数格子和偶数格子?$

$很容易想到,奇数偶数形成一个二分图,那么奇数放左边,偶数放右边$

$Ⅱ.每个点都要被覆盖,想到了什么?$

$以前做路径覆盖是拆点为入点和出点,这里也不例外$

$首先,空格子必定有边到入点,也有边到出点(不管成环还是作为奇偶路径)$

$奇数只能作为路径的开头,所以只需要有入点覆盖$

$偶数只能作为路径结尾,所以只需要有出点覆盖$

总结

把每个点拆成入点和出点

源点s向奇数格子和空格子的入点连流量1,费用0的边

偶数格子和空格子的出点向汇点t连流量1,费用0的边

每个格子的入点向上下左右连流量1,费用cost的边(cost题目给出)

$可以发现这样连边是个二分图$

$左边是奇数入点和空格入点$

$右边是偶数出点和空格出点,我们只是跑了一遍最小费用最大流(二分图匹配)$

$为什么结果是对的呢??$

$Ⅰ.首先,如果满流,说明每个奇数从源点流入,偶数点流出汇点(保证奇偶路径)$

$Ⅱ.然后源点必定流入每个空格子的入点,从空格子出点入到汇点$

$Ⅰ保证了奇偶路径的合法,相当于你把某些二分图匹配对拼起来就是奇数开头偶数结尾的路径$

$Ⅱ保证了环的合法性,假设是一条链,势必存在开头末尾只有一个入度,那就不会满流$

$最后一个问题了,题目中说2个点也算环,但是需要计算2次花费!!$

$这个没必要考虑$

$假如a,b两个点成环$

$一个匹配是是源点流入a入点再从b出点流到汇点$

$另一个匹配是源点流入b入点再流入a出点,最后流进汇点$

$其实花费已经计算了两次$

非常巧妙地构图方式,果然我网络流还是个菜鸡

#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; const int inf=1e9; #define id(x,y) (x-1)*m+y int n,m,s,t,a[59][59]; 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],vis[maxn],pre[maxn],flow[maxn]; bool spfa() { for(int i=0;i<=t;i++) dis[i]=inf; queue<int>q; dis[s]=0; q.push(s); flow[s]=inf; 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( d[i].flow&&dis[v]>dis[u]+d[i].w ) { 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 main() { int T,casenum=0; cin >> T; while( T-- ) { cin >> n >> m; s=0,t=n*m*2+1; int mincost=0,maxflow=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin >> a[i][j]; if( a[i][j]%2==1||a[i][j]==0 ) add(s,id(i,j),1,0),maxflow--; if( a[i][j]%2==0 ) add(id(i,j)+n*m,t,1,0); } for(int i=1;i<n;i++) for(int j=1;j<=m;j++) { int cost; cin >> cost; add(id(i,j),id(i+1,j)+n*m,1,cost); add(id(i+1,j),id(i,j)+n*m,1,cost); } for(int i=1;i<=n;i++) for(int j=1;j<m;j++) { int cost; cin >> cost; add(id(i,j),id(i,j+1)+n*m,1,cost); add(id(i,j+1),id(i,j)+n*m,1,cost); } while( spfa() ) { int x=t,i; 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; } } printf("Case #%d: ",++casenum); if( maxflow!=0 ) cout << -1 << '\n'; else cout << mincost << '\n'; cnt=1; for(int i=0;i<=t;i++) head[i]=0; } }