[BZOJ3894]文理分科(最小割)

(1) 对每个位置建一个点F1，S向这个点连art[i][j]的边，这个点向T连science[i][j]的边。

(2) 对每个位置再建一个点F2，S向这个点连same_art[i][j]的边，这个点向F1的相邻的五个点连inf的边。

(3) 对每个位置再建一个点F3，这个点向T连same_science[i][j]的边，F1的相邻的五个点向这个点连inf的边。

先让ans等于所有art,science,same_art,same_science的和，减去最大流就是答案。

可以这么理解：

首先ans是将所有收益全部占全的答案，现在要减去的是冲突的收益。冲突分三种，一个点不能既选art又选science，只有相邻五个全部选同一科才会触发same收益，同一个点的两个same收益不可能同时触发。我们的建图只需要满足这三种情况都不出现即可。

第一种冲突显然由(1)直接解决了。

第二种冲突由(2)和(3)解决，可以发现，inf边肯定不会被割掉，也就是说“same[i][j]”和“i,j的五个相邻点存在选另一科”这两个只能选一个。

第三种冲突也很显然，一个点不可能art[i][j]和science[i][j]都不被割掉。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 4 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])
 5 using namespace std;
 6 
 7 const int N=30010,M=400010,K=110,inf=1000000000;
 8 int n,m,ans,x,S,T,tot,cnt=1,F1[K][K],F2[K][K],F3[K][K];
 9 int to[M],f[M],nxt[M],h[N],dis[N],q[M];
10 
11 void add(int u,int v,int w){
12     to[++cnt]=v; f[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt;
13     to[++cnt]=u; f[cnt]=0; nxt[cnt]=h[v]; h[v]=cnt;
14 }
15 
16 bool bfs(){
17     rep(i,0,T) dis[i]=0; q[1]=S; dis[S]=1;
18     for (int st=0,ed=1; st<ed; ){
19         int x=q[++st];
20         For(i,x) if (f[i] && !dis[k=to[i]]) dis[k]=dis[x]+1,q[++ed]=k;
21     }
22     return dis[T];
23 }
24 
25 int dfs(int x,int lim){
26     if (x==T) return lim;
27     int c=0;
28     For(i,x) if (f[i] && dis[k=to[i]]==dis[x]+1){
29         int t=dfs(k,min(lim-c,f[i]));
30         c+=t; f[i]-=t; f[i^1]+=t;
31         if (c==lim) return c;
32     }
33     if (!c) dis[x]=-1;
34     return c;
35 }
36 
37 int main(){
38     freopen("bzoj3894.in","r",stdin);
39     freopen("bzoj3894.out","w",stdout);
40     scanf("%d%d",&n,&m); S=3*n*m+1; T=3*n*m+2;
41     rep(i,1,n) rep(j,1,m) scanf("%d",&x),ans+=x,add(S,F1[i][j]=++tot,x);
42     rep(i,1,n) rep(j,1,m) scanf("%d",&x),ans+=x,add(F1[i][j],T,x);
43     rep(i,1,n) rep(j,1,m){
44         scanf("%d",&x); ans+=x;
45         add(S,F2[i][j]=++tot,x); add(F2[i][j],F1[i][j],inf);
46         if (i>1) add(F2[i][j],F1[i-1][j],inf);
47         if (i<n) add(F2[i][j],F1[i+1][j],inf);
48         if (j>1) add(F2[i][j],F1[i][j-1],inf);
49         if (j<m) add(F2[i][j],F1[i][j+1],inf);
50     }
51     rep(i,1,n) rep(j,1,m){
52         scanf("%d",&x); ans+=x;
53         add(F3[i][j]=++tot,T,x); add(F1[i][j],F3[i][j],inf);
54         if (i>1) add(F1[i-1][j],F3[i][j],inf);
55         if (i<n) add(F1[i+1][j],F3[i][j],inf);
56         if (j>1) add(F1[i][j-1],F3[i][j],inf);
57         if (j<m) add(F1[i][j+1],F3[i][j],inf);
58     }
59     while (bfs()) ans-=dfs(S,inf);
60     printf("%d
",ans);
61     return 0;
62 }

[BZOJ3894]文理分科(最小割)

相关推荐