bzoj3894 文理分科（網絡流最小割）

2019-11-11 01:30:29

字體：大中小

來源：轉載

供稿：網友

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

分析： 1.對于這種n選1可以得到一些收益，并且在一些特殊情況下有更多收益的，一般判斷為網絡流。而處理沖突情況，一般通過添加一條inf邊來表示。這個題目直接正向求不好求，于是我們選擇將總收益減去最小代價。 2.那么我們令S為學文，T為學理，對于額外的收入，加入一個新的點。這里寫圖片描述 3.而具體的來說，對于這個圖，x表示一個學生，與S連通表示學文，與T連通表示學理。y表示新加的點，用來計算同時學理的額外收益，與S連通表示不要額外收益，與T連通表示要額外收益先算出總收益，在用最小割減去即可。 4.于是我們可以列出方程：

c+d=B[i]+WB(學生i學文，不要額外收益，損失學理收益，損失額外收益)a+b=A[i](學生i學理，要額外收益，損失學文收益)b+f+c=inf(學生i學文，要額外收益)a+e+d=A[i]+WB（學生學理，不要額外收益，損失學文收益，損失學理額外收益）

解得：

a=A[i]b=0c=B[i]d=WBe=0f=inf

同時學文類似，只是方向不同，收益不同。

5.所以，最終的建圖就是：

step 1 S向每一個學生連邊，容量為學文的收益，每個學生再向T連邊，容量為學理的收益。step 2 S向代表相鄰5個人都學文收益點連邊，容量為同時學文的收益step 3 該點再向對應5個人連邊，容量為inf，表示只要有人學理，就必須割掉同時學文的收益step 4 學理類似#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;const int maxm=1000010;const int maxn=300010;const int INF=1e9;int to[maxm],Next[maxm],Begin[maxn],w[maxm],e;int n,m;int art[110][110],sci[110][110],same_art[110][110],same_sci[110][110];int id[110][110],gap[maxn],d[maxn];int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};int s,t;int sum;void addedge(int x,int y,int z){ to[++e]=y; Next[e]=Begin[x]; Begin[x]=e; w[e]=z;}void add(int x,int y,int z){ addedge(x,y,z);addedge(y,x,0);}int isap(int x,int flow){ if(x==t) return flow; int res=flow; int v; for(int i=Begin[x];i;i=Next[i])if(w[i]>0 && d[x]==d[v=to[i]]+1){ int Min=isap(v,min(res,w[i])); w[i]-=Min;w[i^1]+=Min; res-=Min; if(!res) return flow; } if(!(--gap[d[x]])) d[s]=t; ++gap[++d[x]]; return flow-res;}int cnt;bool pd(int x,int y){ return x>=1 && x<=n && y>=1 && y<=m;}int main(){ scanf("%d%d",&n,&m); e=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) id[i][j]=++cnt; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&art[i][j]),sum+=art[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&sci[i][j]),sum+=sci[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&same_art[i][j]),sum+=same_art[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&same_sci[i][j]),sum+=same_sci[i][j]; s=cnt*3+1;t=s+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int tmp=(id[i][j]-1)*3; add(s,tmp+1,art[i][j]); add(tmp+1,t,sci[i][j]); add(s,tmp+2,same_art[i][j]); for(int k=0;k<5;k++){ int tx=i+dx[k],ty=j+dy[k]; if(!pd(tx,ty)) continue; add(tmp+2,3*(id[tx][ty]-1)+1,INF); } add(tmp+3,t,same_sci[i][j]); for(int k=0;k<5;k++){ int tx=i+dx[k],ty=j+dy[k]; if(!pd(tx,ty)) continue; add(3*(id[tx][ty]-1)+1,tmp+3,INF); } } int maxflow=0; for(gap[0]=t;d[s]<t;){ maxflow+=isap(s,INF); } ^_^