首页 > 代码库 > bzoj3894: 文理分科

bzoj3894: 文理分科

题意:给一个n*m的网格图,每个点被染黑有一个收益,染白有一个收益,如果这个点相邻(有公共边)的格子与它同色,又会有一个额外收益,求最大收益方案。

考虑类似最大闭合子图的思路,我们将总收益先算出来,然后跑最小割,最后用总收益减掉最小割即为答案。

怎么建图呢?我们要保证一个点选文科后,它周围选理科的点不能有理科额外收益,选理科也同理。

考虑这么建图:每个点拆成3个点,拆出来的第一个点向它周围的点连INF,同时该点本身向拆出来的第一个点连文科额外值,拆出来第二个点与第一个点相反,即被第一个点连到的点(相邻的点)向它连INF,然后被拆出来的第二个点向本体连理科额外值。每个点本体,S向其连文科加上文科额外值,其向T连理科加上理科额外值。

仔细思考,会发现这样能使:一旦周围中出了一个叛徒,被多算的额外值就会被扣除掉。

一开始也想到了最小割来做,但始终解决不了怎么去掉多余的额外值(因为想的是只拆一个点),再次%ihopenot。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 200005
 4 #define INF 1e9
 5 #define id(x,y) (((x)-1)*m+(y))
 6 inline int read(){
 7     int x=0,f=1; char a=getchar();
 8     while(a<0 || a>9) {if(a==-) f=-1; a=getchar();}
 9     while(a>=0 && a<=9) x=x*10+a-0,a=getchar();
10     return x*f;
11 }
12 const int dir[4][2]={1,0,-1,0,0,1,0,-1};
13 int S,T,P,n,m,cur[N],head[N],ans,cnt,d[N],si[105][105],ai[105][105],alls[105][105],alla[105][105];
14 bool vis[N];
15 queue<int>Q;
16 struct edges{
17     int to,cap,flow,next;
18 }e[2*N];
19 inline void insert(int u,int v,int c){
20     e[cnt]=(edges){v,c,0,head[u]};head[u]=cnt++;
21     e[cnt]=(edges){u,0,0,head[v]};head[v]=cnt++;
22 }
23 inline bool bfs(){
24     memset(vis,0,sizeof(vis));
25     d[S]=0; Q.push(S); vis[S]=1;
26     while(!Q.empty()){
27         int x=Q.front(); Q.pop();
28         for(int i=head[x];i>=0;i=e[i].next)
29             if(!vis[e[i].to] && e[i].cap>e[i].flow)
30                 d[e[i].to]=d[x]+1,vis[e[i].to]=1,Q.push(e[i].to);
31     }
32     return vis[T];
33 }
34 int dfs(int x,int a){
35     if(x==T || !a) return a;
36     int f,flow=0;
37     for(int& i=cur[x];i>=0;i=e[i].next){
38         if(d[e[i].to]==d[x]+1 && (f=dfs(e[i].to,min(a,e[i].cap-e[i].flow)))>0)
39         e[i].flow+=f,flow+=f,e[i^1].flow-=f,a-=f;
40         if(!a) break;
41     }
42     return flow;
43 }
44 inline int maxflow(){
45     int flow=0;
46     while(bfs()){
47         for(int i=S;i<=T;i++) cur[i]=head[i];
48         flow+=dfs(S,INF);
49     }
50     return flow;
51 }
52 int main(){
53     memset(head,-1,sizeof(head));
54     n=read(); m=read(); S=0; T=3*n*m+1; P=n*m;
55     for(int i=1;i<=n;i++)
56         for(int j=1;j<=m;j++)
57             ai[i][j]=read(),ans+=ai[i][j];
58     for(int i=1;i<=n;i++)
59         for(int j=1;j<=m;j++)
60             si[i][j]=read(),ans+=si[i][j];
61     for(int i=1;i<=n;i++)
62         for(int j=1;j<=m;j++)
63             alla[i][j]=read(),ans+=alla[i][j];
64     for(int i=1;i<=n;i++)
65         for(int j=1;j<=m;j++)
66             alls[i][j]=read(),ans+=alls[i][j];
67     for(int i=1;i<=n;i++)
68         for(int j=1;j<=m;j++){
69             insert(S,id(i,j),ai[i][j]+alla[i][j]);
70             insert(id(i,j),T,si[i][j]+alls[i][j]);
71             insert(id(i,j),id(i,j)+P,alla[i][j]);
72             insert(id(i,j)+2*P,id(i,j),alls[i][j]);
73             for(int x,y,k=0;k<4;k++){
74                 x=i+dir[k][0],y=j+dir[k][1];
75                 if(x<1 || x>n || y<1 || y>m) continue;
76                 insert(id(i,j)+P,id(x,y),INF);
77                 insert(id(x,y),id(i,j)+2*P,INF);
78             }
79         }
80     printf("%d\n",ans-maxflow());
81     return 0;
82 } 

 

bzoj3894: 文理分科