【最小割】BZOJ3894-文理分科

【题目大意】

给定一个m*n的矩阵，每个格子的人可以学文或者学理，学文和学理各有一个满意度，如果以某人为中心的十字内所有人都学文或者学理还会得到一个额外满意度，求最大满意度之和。

【思路】

发现这道题那么久（比划——）之前交过没A。强迫症先水过填个坑。懒得写题解了，都是套路。思路类似于以前的小M的农作物，戳：★

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<vector>
  7 #define S 0
  8 #define T m*n*3+1 
  9 using namespace std;
 10 const int INF=0x7fffffff;
 11 const int MAXN=3*100*100+50;
 12 struct node
 13 {
 14     int to,pos,cap;
 15 };
 16 int m,n,ans; 
 17 vector<node> E[MAXN];
 18 int dis[MAXN];
 19 int dx[4]={1,-1,0,0};
 20 int dy[4]={0,0,1,-1};
 21  
 22 void addedge(int u,int v,int w)
 23 {
 24     E[u].push_back((node){v,E[v].size(),w});
 25     E[v].push_back((node){u,E[u].size()-1,0});
 26 }
 27  
 28 bool bfs()
 29 {
 30     memset(dis,-1,sizeof(dis));
 31     queue<int> que;
 32     while (!que.empty()) que.pop(); 
 33     que.push(S);
 34     dis[S]=0;
 35     while (!que.empty())
 36     {
 37         int head=que.front();que.pop();
 38         if (head==T) return true;  
 39         for (int i=0;i<E[head].size();i++)
 40         {
 41             node tmp=E[head][i];
 42             if (dis[tmp.to]==-1 && tmp.cap)
 43             {
 44                 dis[tmp.to]=dis[head]+1;
 45                 que.push(tmp.to);
 46             }
 47         }
 48     }
 49     return false;
 50 }
 51  
 52 int dfs(int s,int e,int f)
 53 {
 54     if (s==e) return f;
 55     int ret=0;
 56     for (int i=0;i<E[s].size();i++)
 57     {
 58         node &tmp=E[s][i];
 59         if (dis[tmp.to]==dis[s]+1 && tmp.cap)
 60         {
 61             int delta=dfs(tmp.to,e,min(f,tmp.cap));
 62             if (delta>0)
 63             {
 64                 tmp.cap-=delta;
 65                 E[tmp.to][tmp.pos].cap+=delta;
 66                 f-=delta;
 67                 ret+=delta;
 68                 if (f==0) return ret;
 69             }
 70             else dis[tmp.to]=-1;
 71         }
 72     } 
 73     return ret;
 74 }
 75  
 76 void dinic()
 77 {
 78     while (bfs())
 79     {
 80         int f=dfs(S,T,INF);
 81         if (f) ans-=f;else break;
 82     }
 83     printf("%d
",ans);
 84 }
 85 
 86 void init()
 87 {
 88     scanf("%d%d",&n,&m);
 89     ans=0;
 90     for (int i=1;i<=n;i++)
 91         for (int j=1;j<=m;j++)
 92         {
 93             int now=(i-1)*m+j,art;
 94             scanf("%d",&art);
 95             addedge(S,now,art);
 96             ans+=art;
 97         }
 98     for (int i=1;i<=n;i++)
 99         for (int j=1;j<=m;j++)
100         {
101             int now=(i-1)*m+j,science;
102             scanf("%d",&science);
103             addedge(now,T,science);
104             ans+=science;
105         }
106         
107     int cnt=m*n,same;
108     for (int i=1;i<=n;i++)
109         for (int j=1;j<=m;j++)
110         {
111             ++cnt;
112             scanf("%d",&same);
113             addedge(S,cnt,same);
114             ans+=same;
115             addedge(cnt,(i-1)*m+j,INF);
116             for (int k=0;k<4;k++)
117             {
118                 int nowx=i+dx[k],nowy=j+dy[k];
119                 if (nowx>=1 && nowx<=n && nowy>=1 && nowy<=m)
120                     addedge(cnt,(nowx-1)*m+nowy,INF);
121             }
122         }
123     for (int i=1;i<=n;i++)
124         for (int j=1;j<=m;j++)
125         {
126             ++cnt;
127             scanf("%d",&same);
128             addedge(cnt,T,same);
129             ans+=same;
130             addedge((i-1)*m+j,cnt,INF);
131             for (int k=0;k<4;k++)
132             {
133                 int nowx=i+dx[k],nowy=j+dy[k];
134                 if (nowx>=1 && nowx<=n && nowy>=1 && nowy<=m)
135                     addedge((nowx-1)*m+nowy,cnt,INF);
136             }
137         }
138 }
139  
140 int main()
141 {
142     init();
143     dinic();
144     return 0;
145 }