Description 文理分科是一件很糾結(jié)的事情！（雖然看到這個題目的人肯定都沒有糾結(jié)過） 小P所在的班級要進(jìn)行文理分科。他的班級可以用一個n*m的矩陣進(jìn)行描述,每個格子代表一個同學(xué)的座位。每位同學(xué)必須從文科和理科中選擇一科。同學(xué)們在選擇科目的時(shí)候會獲得一個滿意值。滿意值按如下的方式得到： 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)該如何選擇，才能使所有人的滿意值之和最大。請告訴他這個最大值。
分析： 1.對于這種n選1可以得到一些收益，并且在一些特殊情況下有更多收益的，一般判斷為網(wǎng)絡(luò)流。而處理沖突情況，一般通過添加一條inf邊來表示。 這個題目直接正向求不好求，于是我們選擇將總收益減去最小代價(jià)。 2.那么我們令S為學(xué)文，T為學(xué)理，對于額外的收入，加入一個新的點(diǎn)。 
3.而具體的來說，對于這個圖，x表示一個學(xué)生，與S連通表示學(xué)文，與T連通表示學(xué)理。y表示新加的點(diǎn)，用來計(jì)算同時(shí)學(xué)理的額外收益，與S連通表示不 要額外收益，與T連通表示要額外收益先算出總收益，在用最小割減去即可。 4.于是我們可以列出方程：
解得：
a=A[i]b=0c=B[i]d=WBe=0f=inf同時(shí)學(xué)文類似，只是方向不同，收益不同。
5.所以，最終的建圖就是：
step 1 S向每一個學(xué)生連邊，容量為學(xué)文的收益，每個學(xué)生再向T連邊，容量為學(xué)理的收益。step 2 S向代表相鄰5個人都學(xué)文收益點(diǎn)連邊，容量為同時(shí)學(xué)文的收益step 3 該點(diǎn)再向?qū)?yīng)5個人連邊，容量為inf，表示只要有人學(xué)理，就必須割掉同時(shí)學(xué)文的收益step 4 學(xué)理類似#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); } ^_^新聞熱點(diǎn)
疑難解答
