題目描述
高一一班的座位表是個n*m的矩陣，經過一個學期的相處，每個同學和前后左右相鄰的同學互相成為了好朋友。這學期要分文理科了，每個同學對于選擇文科與理科有著自己的喜悅值，而一對好朋友如果能同時選文科或者理科，那么他們又將收獲一些喜悅值。

作為計算機競賽教練的scp大老板，想知道如何分配可以使得全班的喜悅值總和最大。

輸入格式
第一行兩個正整數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列的同學同時選擇理科獲得的額外喜悅值。

輸出格式
輸出一個整數，表示喜悅值總和的最大值

輸入

1 2 1 1 100 110 1 1000

輸出

1210

說明/提示
【樣例說明】

兩人都選理，則獲得100+110+1000的喜悅值。

對于100%以內的數據，n,m<=100 所有喜悅值均為小于等于5000的非負整數

解題：這道題與luogu P1361是用相同的做法。
這道題的做法是，對于每個同學，連一條邊到理科，連一條邊到文科，而對于其他的矩陣（一個同學和其他同學同時選理科或文科得到的值），新建一個點，然后連向相應的分科的點，最后我們選擇割一條邊，就相當于將那個點割到一個集合，我們要求剩下的值最大，也就是減去最少的邊，使得源點和匯點不連通，所以求最小割即可。

代碼：

#pragma GCC optimize(2) #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <string> #include <vector> #include <set> #include <map> #include <stack> #include <bitset> #include <queue> #include <cstdio> //#include <random> #include <time.h> using namespace std; //std::mt19937 rnd(233); #define pp pair<int,int> #define ull unsigned long long #define ls root<<1 #define rs root<<1|1 //#define int long long typedef long long ll; const int inf = 0x3f3f3f3f; const int NINF = 0xc0c0c0c0; const int maxn =1e5+7; const int Maxn = 5e6+7; const double eps=1e-6; const int mod=1e9+7; struct edge{int v,w,next; }e[Maxn]; int head[maxn],cnt=1,cur[maxn],n,m,s,t,dis[maxn]; int tot; void add(int a,int b,int c){e[++cnt]=edge{b,c,head[a]};head[a]=cnt;//cout<<a<<' '<<b<<' '<<c<<endl; } bool bfs(){for(int i=0;i<=tot+1;i++)dis[i]=0;dis[s]=1;queue<int> q;q.push(s);//cout<<s<<endl;while(q.size()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].next){int v=e[i].v,w=e[i].w;if(w>0 && !dis[v]){dis[v]=dis[u]+1;q.push(v);if(v==t)return 1;}}}return 0; }int dfs(int u,int flow){//if(u==t)cout<<"---";//cout<<flow<<endl;if(!flow || u==t)return flow;int tflow=0;for(int i=head[u];i;i=e[i].next){cur[u]=e[i].next;int v=e[i].v,w=e[i].w;if(!w)continue;if(dis[v]!=dis[u]+1)continue;int tmp=dfs(v,min(flow,w));e[i].w-=tmp;e[i^1].w+=tmp;flow-=tmp;tflow+=tmp;if(!flow)break;}if(!tflow)dis[u]=0;return tflow; }signed main(){scanf("%d%d",&n,&m);s=0,t=n*m+2*n*(m-1)+2*(n-1)*m+1;//cout<<t<<endl;tot=n*m;int res=0,x;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&x);res+=x;int a=(i-1)*m+j;add(s,a,x);add(a,s,0);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&x);res+=x;int a=(i-1)*m+j;add(a,t,x);add(t,a,0);}for(int i=1;i<n;i++)for(int j=1;j<=m;j++){++tot;scanf("%d",&x);res+=x;int a=(i-1)*m+j;add(s,tot,x);add(tot,s,0);add(tot,a,inf);add(a,tot,0);add(tot,a+m,inf);add(a+m,tot,0);}for(int i=1;i<n;i++)for(int j=1;j<=m;j++){++tot;scanf("%d",&x);res+=x;int a=(i-1)*m+j;add(tot,t,x);add(t,tot,0);add(a,tot,inf);add(tot,a,0);add(a+m,tot,inf);add(tot,a+m,0);}for(int i=1;i<=n;i++)for(int j=1;j<m;j++){++tot;scanf("%d",&x);res+=x;int a=(i-1)*m+j;add(s,tot,x);add(tot,s,0);add(tot,a,inf);add(a,tot,0);add(tot,a+1,inf);add(a+1,tot,0);}for(int i=1;i<=n;i++)for(int j=1;j<m;j++){++tot;scanf("%d",&x);res+=x;int a=(i-1)*m+j;add(tot,t,x);add(t,tot,0);add(a,tot,inf);add(tot,a,0);add(a+1,tot,inf);add(tot,a+1,0);}int ans=0,flow;while(bfs()){//for(int i=0;i<=tot;i++)cur[i]=head[i];while(flow=dfs(s,inf))ans+=flow;//cout<<"--"<<endl;}//cout<<res<<' '<<ans<<endl;cout<<res-ans<<endl; }

小記：這道題建圖方法和小M的作物那道題是一樣的，但是寫這道題的時候，還是出了一些問題，最開始找了挺久也沒有找出來，最后重新寫了一遍，但是 因為使用了cur數組，后面的樣例都T了，所以有些時候cur數組對于優化是沒有貢獻的。

總結

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

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