题解 P4313 【文理分科】

Nemlit

2019-01-28 21:12:12

Solution

对于每一个人,要么选文科,要么选理科,典型的非黑即白问题,我们可以用最小割来解决。 又因为最大流=最小割,所以我们可以采用网络流来解决 但是我们怎么建边呢? 因为在这道题中,文理平等,所以我们可以将文科靠近源点,理科靠近汇点 对于每一个same值,我们只要有一个对应点选了另一个科目,那么我们就必须把same值剪掉。 也就是说,如果该边被割,则说明这些人不同时选一个科目,不能获得同时选这门科目可获得的收益。 我们还需要保证不割这条边则必然都选这个科目,我们可以将$(i,j)$’向相邻的那几个点对应的连一条边,长度为inf 这条边一定不会被割掉,也就保证了在都选择相同科目的收益的边不被割时,另一个科目的边会被割掉(不然会有流量一直流)。 ### 具体连边方法如下: 令S集表示学文,T集表示学理 $S$向$(i,j)$连一条容量为$art[i][j]$的边 $(i,j)$向$T$连一条容量为$science[i][j]$的边 对于额外收益,新建一个点$(i,j)$’,向$(i,j)$和相邻四个点各连一条容量为无穷的边 $S$向$(i,j)$’连一条容量为$same_art[i][j]$的边 同时选理科的额外收益同理 每个最小割对应一种方案 答案就是sum-最小割 代码如下: ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",__LINE__) #define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) #define inf 1234567890 #define mod 1000000007 il int read() { re int x=0,f=1;re char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return x*f; } #define maxn 105*105*3 struct edge { int v,w,next; }e[maxn*10]; int fx[5]={1,-1,0,0,0}; int fy[5]={0,0,1,-1,0}; int n,m,head[maxn],cnt=1,S,T,cur[maxn],dep[maxn],sum; int art,sci,saa,sas; queue<int>q; il void add(int u,int v,int w) { e[++cnt]=(edge){v,w,head[u]}; head[u]=cnt; e[++cnt]=(edge){u,0,head[v]}; head[v]=cnt; } il void doit(int x,int y) { for(re int i=0;i<5;++i) { int nx=x+fx[i],ny=y+fy[i]; if(nx<1||ny<1||nx>n||ny>m) continue; add(n*m+(nx-1)*m+ny,(x-1)*m+y,inf); add((x-1)*m+y,2*n*m+(nx-1)*m+ny,inf); } } il bool bfs() { memset(dep,0,sizeof(dep)); memcpy(cur,head,sizeof(head)); q.push(S); dep[S]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(re int i=head[u];i;i=e[i].next) { int v=e[i].v; if(!dep[v]&&e[i].w>0) { dep[v]=dep[u]+1; q.push(v); } } } return dep[T]!=0; } il int dfs(int u,int mi) { if(u==T) return mi; int ans=0; for(re int i=cur[u];i;i=e[i].next) { cur[u]=i; int v=e[i].v; if(e[i].w>0&&dep[v]==dep[u]+1) { int low=dfs(v,min(mi,e[i].w)); if(low>0) { e[i].w-=low,e[i^1].w+=low; mi-=low; ans+=low; } } } return ans; } il int dinic() { int low,ans=0; while(bfs()) { while(low=dfs(S,inf)) ans+=low; } return ans; } int main() { n=read(),m=read(); T=3*n*m+1; for(re int i=1;i<=n;++i) for(re int j=1;j<=m;++j) art=read(),add(S,(i-1)*m+j,art),sum+=art; for(re int i=1;i<=n;++i) for(re int j=1;j<=m;++j) sci=read(),add((i-1)*m+j,T,sci),sum+=sci; for(re int i=1;i<=n;++i) for(re int j=1;j<=m;++j) saa=read(),add(S,n*m+(i-1)*m+j,saa),sum+=saa; for(re int i=1;i<=n;++i) for(re int j=1;j<=m;++j) sas=read(),add(2*n*m+(i-1)*m+j,T,sas),sum+=sas; for(re int i=1;i<=n;++i) for(re int j=1;j<=m;++j) doit(i,j); printf("%d",sum-dinic()); return 0; } ```