Posted by 题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=2127
题解
由于题目要求最大值，只需要将所有输入的满意度的和减去最小割的值即为答案，注意下面题解中对于不同情况下割集的解释。
源点向每个同学连边，容量为该同学选文科的满意度，每个同学向汇点连边，容量为该同学选理科的满意度，割这两条边分别表示不选文科和不选理科；
对于相邻的两个同学\(x,y\)，设他们都选文科的额外满意度为\(w_1\)，都选理科的额外满意度为\(w_2\)，由源点分别向\(x,y\)连边，容量为\(\frac {w_1}2\)，分别记为边\(a,b\)，由\(x,y\)分别向汇点连边，容量为\(\frac {w_2}2\)，分别记为边\(c,d\)；
割\(a,b\)表示两个人都不选文科，割\(c,d\)表示两个人都不选理科；
那如果分别选文、理科呢？这时候两个额外满意度都不会获得；
于是由\(x\)向\(y\)、由\(y\)向\(x\)分别连边，容量为\(\frac {w_1+w_2}2\)，分别记为边\(e,f\)；
割\(a,e,d\)表示\(x\)选理科，\(y\)选文科，割\(b,f,c\)表示\(x\)选文科，\(y\)选理科。
注意合并重边，权值乘\(2\)避免精度问题。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; typedef double db; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } const int maxn=110*110; int n,m,sum,head[maxn],cnt,tot,a[maxn],b[maxn],c[maxn],id[110][110]; struct edge { int v,next,val; }e[maxn*10]; void addedge(int x,int y,int z) { e[cnt]=(edge){y,head[x],z}; head[x]=cnt++; swap(x,y); e[cnt]=(edge){y,head[x],0}; head[x]=cnt++; return; } struct mf { int idx[maxn*3],s,t,cur[maxn*3]; void bfs() { memset(idx,0,sizeof(idx)); queue<int>q; q.push(s); idx[s]=1; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(!e[i].val||idx[v])continue; idx[v]=idx[u]+1; q.push(v); } } return; } int dfs(int u,int _min) { if(u==t)return _min; int ret=0,k; for(int i=cur[u];~i;i=e[i].next) { int v=e[i].v; cur[u]=i; if(!e[i].val||idx[v]!=idx[u]+1)continue; k=dfs(v,min(_min-ret,e[i].val)); e[i].val-=k; e[i^1].val+=k; ret+=k; if(ret==_min)break; } return ret; } int dinic() { int ret=0; while(true) { bfs(); if(!idx[t])break; memcpy(cur,head,sizeof(head)); ret+=dfs(s,inf); } return ret; } }t1; int main() { #ifndef online_judge freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif n=read();m=read(); memset(head,-1,sizeof(head)); t1.t=n*m+1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { int x=read();sum+=x; a[id[i][j]=(i-1)*m+j]=x<<1; } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { int x=read();sum+=x; b[id[i][j]]=x<<1; } for(int i=1;i<n;++i) for(int j=1;j<=m;++j) { int x=read();sum+=x; a[id[i][j]]+=x;a[id[i+1][j]]+=x; c[id[i][j]]=x; } for(int i=1;i<n;++i) for(int j=1;j<=m;++j) { int x=read();sum+=x; b[id[i][j]]+=x;b[id[i+1][j]]+=x; addedge(id[i][j],id[i+1][j],c[id[i][j]]+x); addedge(id[i+1][j],id[i][j],c[id[i][j]]+x); } for(int i=1;i<=n;++i) for(int j=1;j<m;++j) { int x=read();sum+=x; a[id[i][j]]+=x;a[id[i][j+1]]+=x; c[id[i][j]]=x; } for(int i=1;i<=n;++i) for(int j=1;j<m;++j) { int x=read();sum+=x; b[id[i][j]]+=x;b[id[i][j+1]]+=x; addedge(id[i][j],id[i][j+1],c[id[i][j]]+x); addedge(id[i][j+1],id[i][j],c[id[i][j]]+x); } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { addedge(t1.s,id[i][j],a[id[i][j]]); addedge(id[i][j],t1.t,b[id[i][j]]); } printf("%d\n",sum-t1.dinic()/2); return 0; } |