继续网络流的学习。。。。
题意简析：就是给你张图，叫你求最小割。
解题思路：最小割=最大流，按题意见图跑一次就好了。
附代码：
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #define For(i,a,b) for (int i=a; i<=b; i++) #define Ford(i,a,b) for (int i=a; i>=b; i--) #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout); #define mem(qaq,num) memset(qaq,num,sizeof(qaq)); #define ll long long #define mod 1000000007 #define INF 90000000000000 using namespace std; struct zxy{ int next,to; ll v; }edge[6000010]; int n,m,cnt=1,head[1000001],np[1000001],lev[1000001],tt[1000001]; inline int in(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } inline int getno(int x,int y){ return (x-1)*m+y; } inline void ins(int x,int y,int l){ edge[++cnt].to=y,edge[cnt].next=head[x],edge[cnt].v=l,head[x]=cnt; edge[++cnt].to=x,edge[cnt].next=head[y],edge[cnt].v=l,head[y]=cnt; } void read(){ n=in(),m=in(); For(i,1,n) For(j,1,m-1) ins(getno(i,j),getno(i,j+1),in()); For(i,1,n-1) For(j,1,m) ins(getno(i,j),getno(i+1,j),in()); For(i,1,n-1) For(j,1,m-1) ins(getno(i,j),getno(i+1,j+1),in()); return; } inline void bfs(){ int h=0,t=1; mem(lev,0); lev[1]=1; tt[1]=1; do{ h++; int k=head[tt[h]]; while(k){ if (!lev[edge[k].to]&&edge[k].v){ lev[edge[k].to]=lev[tt[h]]+1; tt[++t]=edge[k].to; } k=edge[k].next; } }while(h<t); } ll dfs(int u,int v,ll f){ if (!(u^v)) return f; while(np[u]){ if (lev[edge[np[u]].to]==lev[u]+1&&edge[np[u]].v){ int d=dfs(edge[np[u]].to,v,min(f,edge[np[u]].v)); if (d){ edge[np[u]].v-=d; edge[np[u]^1].v+=d; return d; } } np[u]=edge[np[u]].next; } return 0; } ll work(){ ll flow=0; for(;;){ bfs(); if (!lev[n*m]) return flow; For(i,1,n*m) np[i]=head[i]; ll d=dfs(1,n*m,INF); while(d){ flow+=d; d=dfs(1,n*m,INF); } } } int main(){ read(); printf("%lld",work()); }
本文由Melacau编写，Melacau代表M星向您问好，如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文，请您向我联系，email:13960948839@163.com.