本文共 2724 字，大约阅读时间需要 9 分钟。
【题目分析】
基本上是第一次真正的使用最小割的模型。
同时加上一个数然后最后再减去是处理负数的一种方法。
设立出来最小割的模型然后解方程是一件很重要的事情，建议取一个相对来说比较简单的值带入求解。
这道题目，把收益取反，最小流就是最大的收益了。
需要好好思考
【代码】
#include #include //#include //#include //#include //#include #include //#include //#include //#include using namespace std; #define maxn 105#define maxn2 105*105#define me 800005#define inf 0x3f3f3f3f#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i) void Finout(){ #ifndef ONLINE_JUDGE freopen("nt2011_happiness.in","r",stdin); freopen("nt2011_happiness.out","w",stdout); #endif} int Getint(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;} int h[me<<1],to[me<<1],ne[me<<1],fl[me<<1],en=0,cnt=0,S=0,T,x; void add(int a,int b,int c){to[en]=b; ne[en]=h[a]; fl[en]=c; h[a]=en++;} int map[maxn*maxn]; bool tell(){ queue q; memset(map,-1,sizeof map); map[S]=0; while (!q.empty()) q.pop(); q.push(S); while (!q.empty()) { int x=q.front(); q.pop(); for (int i=h[x];i>=0;i=ne[i]) { if (map[to[i]]==-1&&fl[i]>0) { map[to[i]]=map[x]+1; q.push(to[i]); } } } if (map[T]!=-1) return true; return false;} int zeng(int k,int r){ if (k==T) return r; int ret=0; for (int i=h[k];i>=0&&ret 0) { int tmp=zeng(to[i],min(fl[i],r-ret)); ret+=tmp; fl[i]-=tmp; fl[i^1]+=tmp; } if (!ret) map[k]=-1; return ret;} int n,m,hash[maxn][maxn],ws[maxn2];int wt[maxn2],all=0; int main(){ memset(h,-1,sizeof h); Finout(); n=Getint(); m=Getint(); F(i,1,n) F(j,1,m) hash[i][j]=++cnt;// F(i,1,n)// {// F(j,1,m) printf("%d ",hash[i][j]);// printf("\n");// } T=++cnt; F(i,1,n) F(j,1,m) { x=Getint(); all+=x; wt[hash[i][j]]+=2*x; } F(i,1,n) F(j,1,m) { x=Getint(); all+=x; ws[hash[i][j]]+=2*x; } F(i,1,n-1) F(j,1,m) { x=Getint(); all+=x; wt[hash[i][j]]+=x; wt[hash[i+1][j]]+=x; add(hash[i][j],hash[i+1][j],x); add(hash[i+1][j],hash[i][j],x); } F(i,1,n-1) F(j,1,m) { x=Getint(); all+=x; ws[hash[i][j]]+=x; ws[hash[i+1][j]]+=x; add(hash[i][j],hash[i+1][j],x); add(hash[i+1][j],hash[i][j],x); } F(i,1,n) F(j,1,m-1) { x=Getint(); all+=x; wt[hash[i][j]]+=x; wt[hash[i][j+1]]+=x; add(hash[i][j],hash[i][j+1],x); add(hash[i][j+1],hash[i][j],x); } F(i,1,n) F(j,1,m-1) { x=Getint(); all+=x; ws[hash[i][j]]+=x; ws[hash[i][j+1]]+=x; add(hash[i][j],hash[i][j+1],x); add(hash[i][j+1],hash[i][j],x); }// printf("over!\n"); F(i,1,n) F(j,1,m) { add(S,hash[i][j],ws[hash[i][j]]); add(hash[i][j],S,0); add(hash[i][j],T,wt[hash[i][j]]); add(T,hash[i][j],0); } int ans=0,tmp; while (tell()) while (tmp=zeng(S,inf)) ans+=tmp; printf("%d\n",all-ans/2);}
转载于:https://www.cnblogs.com/SfailSth/p/6344800.html