Description

文理分科是一件很糾結(jié)的事情！（雖然看到這個題目的人肯定都沒有糾結(jié)過）

小P所在的班級要進(jìn)行文理分科。他的班級可以用一個n*m的矩陣進(jìn)行 描述，每個格子代表一個同學(xué)的座位。每位同學(xué)必須從文科和理科中選擇 一科。同學(xué)們在選擇科目的時候會獲得一個滿意值。滿意值按如下的方式 得到： 1．如果第i行第秒J的同學(xué)選擇了文科，則他將獲得art[i][j]的滿意值，如 果選擇理科，將得到science[i][j]的滿意值。 2．如果第i行第J列的同學(xué)選擇了文科，并且他相鄰（兩個格子相鄰當(dāng)且 僅當(dāng)它們擁有一條相同的邊）的同學(xué)全部選擇了文科，則他會更開 心，所以會增加same_art[i][j]的滿意值。 3．如果第i行第j列的同學(xué)選擇了理科，并且他相鄰的同學(xué)全部選擇了理 科，則增加same_science[i][j]的滿意值。 小P想知道，大家應(yīng)該如何選擇，才能使所有人的滿意值之和最大。請 告訴他這個最大值。

Solution

?妹主席在JZYZ講過的一道，想起來了于是去切一下

“依然是把最大化收益轉(zhuǎn)化為最小化得不到的收益。
對于每個點(diǎn)，向S和T分別連容量為ai,bi的邊，那么V代表劃分到A集合的點(diǎn)，V’代表c[s,V’]代表劃分到B集合中的元素失去的ai收益，c[V,t]相反，因?yàn)檫x到A集合的點(diǎn)和選到B集合的點(diǎn)相互之間不會產(chǎn)生影響，所以c[V,V’]=0
對于每個附加條件我們額外建立一個點(diǎn)，假設(shè)是要求一些元素必須劃分到A集合中，那么從源點(diǎn)向它連一條容量為ci的邊，從它向要求的元素連一條容量為正無窮的邊，這樣，割掉源點(diǎn)連向它的邊（舍棄掉這個收益）和割掉它連向的所有點(diǎn)連向匯點(diǎn)的邊（舍棄掉這些點(diǎn)劃分到bi的收益）必須選擇其中一個。
點(diǎn)數(shù)為O(n+m)，邊數(shù)為O(n+m+sigma(|S|))”
——妹主席的教誨

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #define Max(a,b) (a>b?a:b) #define Min(a,b) (a<b?a:b) #define INF 0x3f3f3f3f using namespace std; int n,m,s,t,level[50005],head[50005],cnt=0,ans=0; int dx[5]={1,-1,0,0,0},dy[5]={0,0,1,-1,0}; struct Node{int next,to,cap; }Edges[1000005]; int Read() {int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } void addedge(int u,int v,int c) {Edges[cnt].next=head[u];head[u]=cnt;Edges[cnt].to=v;Edges[cnt++].cap=c; } void Insert(int u,int v,int c) {addedge(u,v,c);addedge(v,u,0); } int number(int i,int j) {return (i-1)*m+j; } bool bfs() {memset(level,-1,sizeof(level));queue<int>q;q.push(s);level[s]=0;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];~i;i=Edges[i].next){int v=Edges[i].to;if(level[v]==-1&&Edges[i].cap)level[v]=level[u]+1,q.push(v);}}if(level[t]==-1)return false;return true; } int dfs(int u,int Maxflow) {if(u==t)return Maxflow;int flow=0,d;for(int i=head[u];~i&&Maxflow>flow;i=Edges[i].next){int v=Edges[i].to;if(level[v]==level[u]+1&&Edges[i].cap){d=dfs(v,Min(Maxflow-flow,Edges[i].cap));Edges[i].cap-=d;Edges[i^1].cap+=d;flow+=d;}}if(!flow)level[u]=-1;return flow; } int Dinic() {int res=0,d;while(bfs()){while(d=dfs(s,INF))res+=d;}return res; } int main() {memset(head,-1,sizeof(head));n=Read(),m=Read();s=0,t=3*n*m+1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int art=Read();ans+=art;Insert(s,number(i,j),art);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int science=Read();ans+=science;Insert(number(i,j),t,science);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int same_art=Read(),p=number(i,j)+m*n;ans+=same_art;Insert(s,p,same_art);for(int k=0;k<5;k++){if(i+dx[k]>0&&i+dx[k]<=n&&j+dy[k]>0&&j+dy[k]<=m)Insert(p,number(i+dx[k],j+dy[k]),INF);}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int same_science=Read(),p=number(i,j)+2*m*n;ans+=same_science;Insert(p,t,same_science);for(int k=0;k<5;k++){if(i+dx[k]>0&&i+dx[k]<=n&&j+dy[k]>0&&j+dy[k]<=m)Insert(number(i+dx[k],j+dy[k]),p,INF);}}printf("%d\n",ans-Dinic());return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Zars19/p/6694937.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ 3894]文理分科（最小割）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。