题面
很容易看出来是最小割,然后打出模板后发现答案错了(甚至建边都是x->y,我佛了看了半天),一看题解才知道无向图不一样,建图反向边权值也是val,虽然不知道为啥,不过说的是本来就可以增广
记住就行????
#include<bits/stdc++.h> using namespace std; const int maxn=1000005; const int maxm=6000005; int n,m; int s,t; int cnt=1,head[maxn]; struct edge{ int x,y,val,next; }e[maxm]; void add(int x,int y,int val){ e[++cnt]=(edge){x,y,val,head[x]}; head[x]=cnt; } void add_edge(int x,int y,int val){ add(x,y,val); add(y,x,val); } int d[maxn]; bool bfs(){ queue<int> q; memset(d,0,sizeof(d)); q.push(s);d[s]=1; while(!q.empty()){ int x=q.front(); q.pop(); for(int i=head[x];i;i=e[i].next){ int y=e[i].y; if(e[i].val&&!d[y]){ d[y]=d[x]+1; q.push(y); if(y==t) return true; } } } return false; } int dfs(int x,int flow){ if(x==t) return flow; int rest=flow,k; for(int i=head[x];i;i=e[i].next){ int y=e[i].y; if(e[i].val&&d[y]==d[x]+1){ k=dfs(y,min(rest,e[i].val)); if(!k) {d[y]=0;continue;} e[i].val-=k; e[i^1].val+=k; rest-=k; if(!rest) break; } } return flow-rest; } int dinic(){ int ret=0; while(bfs()) ret+=dfs(s,0x3f3f3f); return ret; } int main(){ scanf("%d%d",&n,&m); s=1;t=n*m; for(int i=1;i<=n;i++) for(int j=1;j<m;j++){ int val; scanf("%d",&val); add_edge((i-1)*m+j,(i-1)*m+j+1,val); } for(int i=1;i<n;i++) for(int j=1;j<=m;j++){ int val; scanf("%d",&val); add_edge((i-1)*m+j,i*m+j,val); } for(int i=1;i<n;i++) for(int j=1;j<m;j++){ int val; scanf("%d",&val); add_edge((i-1)*m+j,i*m+j+1,val); } printf("%d",dinic()); }狼抓兔子