洛谷P1646 [国家集训队]happiness【网络流二元关系】

题目描述：

高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。
作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
n,m<=100

题目分析：

不妨令上图中的$a,c$a,c分别表示选第一个人选文科和理科的收益（记为$w_i,l_i$wi​,li​），$b,d$b,d分别表示第二个人选文科和理科的收益（记为$w_j,l_j$wj​,lj​）。同时选文/理科的收益记为$sw,sl$sw,sl。
先将所有的收益全部加到答案中，$a+b$a+b即表示两人同时选理科的代价，于是有$a+b=w_i+w_j+sw$a+b=wi​+wj​+sw，同理，可以列出如下式子：
$\begin{aligned}a+b&=w_i+w_j+sw\quad\quad\quad\quad&(1) \\ c+d&=l_i+l_j+sl&(2)\\ a+d+f&=w_i+l_j+sw+sl&(3)\\ b+c+e&=l_i+w_j+sw+sl&(4) \end{aligned}$a+bc+da+d+fb+c+e​=wi​+wj​+sw=li​+lj​+sl=wi​+lj​+sw+sl=li​+wj​+sw+sl​(1)(2)(3)(4)​

此处可以得到$e+f=sw+sl>0$e+f=sw+sl>0，故可以直接建图，下面是可行的一组解：
$\begin{aligned}a&=w_i+\frac {sw}2\\ b&=w_j+\frac {sw}2\\ c&=l_i+\frac {sl}2\\ d&=l_j+\frac {sl}2\\ e=f&=\frac {sw+sl}2 \end{aligned}$abcde=f​=wi​+2sw​=wj​+2sw​=li​+2sl​=lj​+2sl​=2sw+sl​​
为了方便，将所有边权乘以2，最后答案再除以2即可。注意每个点连向S,T的边中$w_i,l_i$wi​,li​只记一次，而$sw$sw和$sl$sl是累加。

Code：

#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
#include<algorithm>
#define LL long long
#define maxn 10005
#define maxm 120005
using namespace std;
char cb[1<<15],*cs,*ct;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
inline void read(int &a){
    char c;while(!isdigit(c=getc()));
    for(a=c-'0';isdigit(c=getc());a=a*10+c-'0');
}
const int inf = 0x3f3f3f3f;
int n,m,S,T;
int fir[maxn],cur[maxn],dis[maxn],nxt[maxm],to[maxm],tot=1,cap[maxm],sum;
inline void line(int x,int y,int z,int rz=0){
    nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y,cap[tot]=z;
    nxt[++tot]=fir[y],fir[y]=tot,to[tot]=x,cap[tot]=rz;
}
queue<int>q;
bool bfs()
{
    memset(dis,0,(T+1)<<2);
    dis[T]=1,q.push(T);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=fir[u];i;i=nxt[i]) if(cap[i^1]&&!dis[to[i]]){
            dis[to[i]]=dis[u]+1;
            q.push(to[i]);
        }
    }
    return dis[S];
}
int dfs(int u,int lim)
{
    if(u==T) return lim;
    int need=lim,delta;
    for(int &i=cur[u];i;i=nxt[i]) if(cap[i]&&dis[u]==dis[to[i]]+1){
        delta=dfs(to[i],min(cap[i],need));
        cap[i]-=delta,cap[i^1]+=delta;
        if(!(need-=delta)) break;
    }
    return lim-need;
}
int Dinic(){
    int flow=0;
    while(bfs()) memcpy(cur,fir,(T+1)<<2),flow+=dfs(S,inf);
    return flow;
}
int x,t1[maxn],t2[maxn],p[105][105],a[105][105];
int main()
{
    read(n),read(m);S=0,T=n*m+1;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) p[i][j]=(i-1)*m+j;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(x),t2[p[i][j]]+=2*x;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(x),t1[p[i][j]]+=2*x;
    for(int i=1;i<n;i++) for(int j=1;j<=m;j++) read(x),t2[p[i][j]]+=x,t2[p[i+1][j]]+=x,a[i][j]+=x;
    for(int i=1;i<n;i++) for(int j=1;j<=m;j++) read(x),t1[p[i][j]]+=x,t1[p[i+1][j]]+=x,line(p[i][j],p[i+1][j],a[i][j]+x,a[i][j]+x),a[i][j]=0;
    for(int i=1;i<=n;i++) for(int j=1;j<m;j++) read(x),t2[p[i][j]]+=x,t2[p[i][j+1]]+=x,a[i][j]+=x;
    for(int i=1;i<=n;i++) for(int j=1;j<m;j++) read(x),t1[p[i][j]]+=x,t1[p[i][j+1]]+=x,line(p[i][j],p[i][j+1],a[i][j]+x,a[i][j]+x),a[i][j]=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) line(S,p[i][j],t1[p[i][j]]),line(p[i][j],T,t2[p[i][j]]),sum+=t1[p[i][j]]+t2[p[i][j]];
    printf("%d",(sum-Dinic())/2);
}