Description
高一一班的座位表是個n*m的矩陣，經過一個學期的相處，每個同學和前後左右相鄰的同學互相成為了好朋友。這學期要分文理科了，每個同學對於選擇文科與理科有著自己的喜悅值，而一對好朋友如果能同時選文科或者理科，那麼他們又將收獲一些喜悅值。作為計算機競賽教練的scp大老板，想知道如何分配可以使得全班的喜悅值總和最大。
Input
第一行兩個正整數n，m。接下來是六個矩陣第一個矩陣為n行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學選擇文科獲得的喜悅值。第二個矩陣為n行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學選擇理科獲得的喜悅值。第三個矩陣為n-1行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i+1行第j列的同學同時選擇文科獲得的額外喜悅值。第四個矩陣為n-1行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i+1行第j列的同學同時選擇理科獲得的額外喜悅值。第五個矩陣為n行m-1列
此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i行第j+1列的同學同時選擇文科獲得的額外喜悅值。第六個矩陣為n行m-1列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i行第j+1列的同學同時選擇理科獲得的額外喜悅值。
Output
輸出一個整數，表示喜悅值總和的最大值
Sample Input
1 2
1 1
100 110
1
1000
Sample Output
1210
【樣例說明】
兩人都選理，則獲得100+110+1000的喜悅值。
【數據規模】
對於100%以內的數據，n,m<=100 所有喜悅值均為小於等於5000的非負整數
本題做法很多，大致有三種：
解法一：
利用最小割考慮。
對於原圖中所有相鄰的兩個人A，B，我們建邊：
s->A:cost[A文]+c[文][A][B]/2,s->B:cost[B文]+c[文][A][B]/2;
A->t:cost[A理]+c[理][A][B]/2,B->t:costB[理]+c[理][A][B]/2;
A<-->B:c[文][A][B]/2+c[理][A][B]/2
這樣會出現兩種割，分別對應兩種相同，一種選文一種選理。
code：
#include
#include
#include
#include
#include
#include
#define maxn 10000
using namespace std;
int n,m;
int s,t;
int tot=1;
int fir[200000],en[200000],nex[200000],f[200000];
void ins(int a,int b,int c,int d){
nex[++tot]=fir[a];
fir[a]=tot;
en[tot]=b;
f[tot]=c;
nex[++tot]=fir[b];
fir[b]=tot;
en[tot]=a;
f[tot]=d;
}
int ch[200][200][2];
int flow;
int d[200000],now[200000],num[200000],pre[200000],his[200000];
void sap(){
flow=0;
for (int i=0;i<=t;i++){
now[i]=fir[i];
d[i]=num[i]=0;
}
num[0]=t;
int aug=0x7fffffff;
bool flag;
int i=s;
while (d[s]0&&d[i]==d[en[k]]+1){
aug=min(aug,f[k]);
flag=true;
now[i]=k;
pre[en[k]]=i;
i=en[k];
if (i==t){
flow+=aug;
while (i!=s){
i=pre[i];
f[now[i]]-=aug;
f[now[i]^1]+=aug;
}
aug=0x7fffffff;
}
break;
}
if (flag) continue;
int k1=0,minn=t;
for (int k=fir[i];k;k=nex[k])
if (f[k]>0&&minn>d[en[k]]){
k1=k;
minn=d[en[k]];
}
now[i]=k1;
if (!--num[d[i]]) return;
d[i]=minn+1;
num[d[i]]++;
if (i!=s){
i=pre[i];
aug=his[i];
}
}
}
int sum=0;
int main(){
// freopen("2127.in","r",stdin);
// freopen("2127.out","w",stdout);
scanf("%d%d",&n,&m);
s=n*m+1,t=n*m+2;
for (int i=1;i<=n;i++) //割文 去理
for (int j=1;j<=m;j++){
scanf("%d",&ch[i][j][0]);
sum+=ch[i][j][0];
ch[i][j][0]*=2;
}
for (int i=1;i<=n;i++) //割理 去文
for (int j=1;j<=m;j++){
scanf("%d",&ch[i][j][1]);
sum+=ch[i][j][1];
ch[i][j][1]*=2;
}
for (int i=1;i<=n-1;i++)
for (int j=1;j<=m;j++){
int tmp;
scanf("%d",&tmp);
sum+=tmp;
ins((i-1)*m+j,i*m+j,tmp,tmp);
ch[i][j][0]+=tmp;
ch[i+1][j][0]+=tmp;
}
for (int i=1;i<=n-1;i++)
for (int j=1;j<=m;j++){
int tmp;
scanf("%d",&tmp);
sum+=tmp;
ins((i-1)*m+j,i*m+j,tmp,tmp);
ch[i][j][1]+=tmp;
ch[i+1][j][1]+=tmp;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m-1;j++){
int tmp;
scanf("%d",&tmp);
sum+=tmp;
ins((i-1)*m+j,(i-1)*m+j+1,tmp,tmp);
ch[i][j][0]+=tmp;
ch[i][j+1][0]+=tmp;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m-1;j++){
int tmp;
scanf("%d",&tmp);
sum+=tmp;
ins((i-1)*m+j,(i-1)*m+j+1,tmp,tmp);
ch[i][j][1]+=tmp;
ch[i][j+1][1]+=tmp;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
ins(s,(i-1)*m+j,ch[i][j][0],0);
ins((i-1)*m+j,t,ch[i][j][1],0);
}
sap();
printf("%d",sum-flow/2);
return 0;
}
解法二：
還是利用最小割考慮。
對於原圖中所有相鄰的兩個人A，B，新建輔助節點C，D，建邊：
s->A:cost[A文]，s->B:cost[B文]；
A->t:cost[A理]，B->t:costB[理]；
C->A:INF;C->B:INF;A->D:INF;B->D:INF; 用來幫助我們表示三種取法。(最大權閉合圖)
S->C:c[文][A][B]；D->T:c[理][A][B];
這樣也只會出現兩種割。
code by gsq:
#include
#include
#include
#include
#include
using namespace std;
int getx()
{
char c;int x;
for (c=getchar();c<'0'||c>'9';c=getchar());
for (x=0;c>='0'&&c<='9';c=getchar())
x=(x<<3)+(x<<1)+c-'0';
return x;
}
bool upmin(int &a,const int &b){return a>b?a=b,1:0;}
const int INF=~0U>>1;
const int MAX_N=50050,MAX_M=1200000;
int first[MAX_N],next[MAX_M],to[MAX_M],f[MAX_M];
int tal=1;
int sum;
void tjb(int x,int y,int F){
if (F!=INF) sum+=F;
next[++tal]=first[x];
first[x]=tal;
to[tal]=y;
f[tal]=F;
next[++tal]=first[y];
first[y]=tal;
to[tal]=x;
f[tal]=0;
}
int pre[MAX_N],cur[MAX_N],dis[MAX_N],gap[MAX_N],his[MAX_N];
int sap(int S,int T,int Size){
for (int i=0;i<=Size;++i)
cur[i]=first[i],
dis[i]=gap[i]=0;
int maxflow=0,aug=INF;
int u=pre[S]=S;
gap[0]=Size;
while (dis[S]
解法三：
將原問題轉化，轉化為：所有人現在都選理，然後每個人選擇變成文會帶來多少收益或損失，利用最大權閉合圖考慮。
同樣的，也要新建輔助節點C,D，如下：
C->A:INF;C->B:INF;A->D:INF;B->D:INF;(C點是指全部選文科，D是指有一個選了文科就要付出“共同選理科的代價”)
剩下的利用最大權閉合圖考慮，用文的獲益減去理得獲益，如果是正的，由s連向他，如果是負的，由他連向t。
code by LDD：
#include
#include
#include
#include
#include
#include
using namespace std;
int get_int(){
int x=0;char c;int t=0;
for (c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
if (c=='-'){t=1;c=getchar();}
for (;c>='0'&&c<='9';c=getchar()){x*=10;x+=c-48;}
if (t) x=-x;return x;
}
bool upmin(int &v,int x){if (x=x2[i][j])
{
zh+=x1[i][j]-x2[i][j];
map1.putx(map1.s,(i-1)*m+j,x1[i][j]-x2[i][j]);
}
else map1.putx((i-1)*m+j,map1.t,x2[i][j]-x1[i][j]);
}
int tot=n*m;
for (int i=1;i<=n-1;i++)
for (int j=1;j<=m;j++)
{
x3[i][j]=get_int();
tot++;
map1.putx(map1.s,tot,x3[i][j]);
zh+=x3[i][j];
map1.putx(tot,(i-1)*m+j,inf);
map1.putx(tot,i*m+j,inf);
}
for (int i=1;i<=n-1;i++)
for (int j=1;j<=m;j++)
{
ans+=x4[i][j]=get_int();
tot++;
map1.putx(tot,map1.t,x4[i][j]);
map1.putx((i-1)*m+j,tot,inf);
map1.putx(i*m+j,tot,inf);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m-1;j++)
{
x5[i][j]=get_int();
tot++;
zh+=x5[i][j];
map1.putx(map1.s,tot,x5[i][j]);
map1.putx(tot,(i-1)*m+j,inf);
map1.putx(tot,(i-1)*m+j+1,inf);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m-1;j++)
{
ans+=x6[i][j]=get_int();
tot++;
map1.putx(tot,map1.t,x6[i][j]);
map1.putx((i-1)*m+j,tot,inf);
map1.putx((i-1)*m+j+1,tot,inf);
}
ans+=zh-map1.sap(tot+2);
printf("%d\n",ans);
}
