來自FallDream的博客，未經允許，請勿轉載，謝謝。

---

高一一班的座位表是個n*m的矩陣，經過一個學期的相處，每個同學和前后左右相鄰的同學互相成為了好朋友。這學期要分文理科了，每個同學對于選擇文科與理科有著自己的喜悅值，而一對好朋友如果能同時選文科或者理科，那么他們又將收獲一些喜悅值。作為計算機競賽教練的scp大老板，想知道如何分配可以使得全班的喜悅值總和最大。 ?n,m<=100

文理分科的模型題....

對于每一個點，假如割到S表示選理科，割到T表示選文科，這兩條邊的邊權顯然，然后對于每一個特殊的條件，建立一個新點。如果表示都選文科獲得的喜悅值，那么從S向他連邊，邊權是喜悅值，然后它向那兩個點連邊，邊權設成INF。理科同理。

最后最小割。

然后去網上搜了搜發現了牛逼做法，對邊權進行變換使得不用建出新點，效率變高。有興趣可以自己看看。

#include<iostream> #include<cstdio> #include<cstring> #define INF 2000000000 #define S 0 #define T 50000 #define num(x,y) ((x-1)*m+y) using namespace std; inline int read() {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 cnt=1,head[T+5],c[T+5],n,m,d[T+5],q[T+5],top=0,id; unsigned int ans=0; struct edge{int to,next,w;}e[T*10];inline void ins(int f,int t,int w) {e[++cnt]=(edge){t,head[f],w};head[f]=cnt;e[++cnt]=(edge){f,head[t],0};head[t]=cnt; }bool bfs() {memset(d,0,sizeof(d));int i,j;for(d[q[top=i=1]=S]=1;i<=top;i++)for(int j=c[q[i]]=head[q[i]];j;j=e[j].next)if(e[j].w&&!d[e[j].to])d[q[++top]=e[j].to]=d[q[i]]+1;return d[T]; }int dfs(int x,int f) {if(x==T)return f;int used=0;for(int&i=c[x];i;i=e[i].next)if(e[i].w&&d[e[i].to]==d[x]+1){int w=dfs(e[i].to,min(e[i].w,f-used));used+=w;e[i].w-=w;e[i^1].w+=w;if(used==f)return f;}return d[x]=-1,used; }int main() {n=read();m=read();id=num(n,m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int x=read();ans+=x;ins(S,num(i,j),x);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int x=read();ans+=x;ins(num(i,j),T,x);}for(int i=1;i<n;i++)for(int j=1;j<=m;j++){int x=read();ans+=x;ins(S,++id,x);ins(id,num(i,j),INF);ins(id,num(i+1,j),INF);}for(int i=1;i<n;i++)for(int j=1;j<=m;j++){int x=read();ans+=x;ins(++id,T,x);ins(num(i,j),id,INF);ins(num(i+1,j),id,INF);}for(int i=1;i<=n;i++)for(int j=1;j<m;j++){int x=read();ans+=x;ins(S,++id,x);ins(id,num(i,j),INF);ins(id,num(i,j+1),INF);}for(int i=1;i<=n;i++)for(int j=1;j<m;j++){int x=read();ans+=x;ins(++id,T,x);ins(num(i,j),id,INF);ins(num(i,j+1),id,INF);}while(bfs()) ans-=dfs(S,INF);printf("%u\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/FallDream/p/bzoj2127.html

總結

以上是生活随笔為你收集整理的[bzoj2127]happiness的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。