网络流和费用流，其实知道如何建图之后就可以直接套板子了，但正如konata所言，这些题如果不是在今天作业里，打死也想不到要用网络流。
善意的投票
这个是最小割的典型问题，把睡午觉视为集合a，即原点，不睡视为集合b，即汇点，那么对每个点，连向自己意愿的容量为1，违背的容量为0。对于一对朋友，他们不在同一个集合会产生1的代价，所以二人间连一条容量为1的双向边（因为两个人中任意一个投与对方不同的票都产生1的代价）。那么问题转化为使s，t位于两个孤立集合的最小代价。跑最大流求最小割即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 305;
const int M = N*(N-1)/2;
#define ll long long
int head[N], nxt[M*2],to[M*2], cnt = 1; ll w[M*2];
int cur[N], dep[N]; queue<int> q;
bool vis[N];
int n, m, s, t; ll maxflow;
void add(int x, int y, int z){
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
w[cnt] = z;
}
bool bfs(){
for(int i = 0; i <= n + 1; i ++){
vis[i] = 0; dep[i] = 0x3fffff; cur[i] = head[i];
}
q.push(s);
dep[s] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
if(dep[v] > dep[x] + 1 && w[i]){
dep[v] = dep[x] + 1;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
}
if(dep[t] != 0x3fffff) return 1;
else return 0;
}
ll dfs(int x,ll flow){
ll rlow = 0;
if(x == t){
maxflow += flow;
return flow;
}
ll used = 0;
for(int i = cur[x]; i; i = nxt[i]){
cur[x] = i;
int v = to[i];
if(dep[v] == dep[x] + 1 && w[i]){
if(rlow = dfs(v, min(flow - used, w[i]) )){
used += rlow;
w[i] -= rlow;
w[i ^ 1] += rlow;
if(used == flow) break;
}
}
}
return used;
}
ll dinic(){
while(bfs()){
dfs(s,0x3fffffff);
}
return maxflow;
}
int main(){
scanf("%d%d",&n,&m);
s = 0, t = n + 1;
for(int i = 1; i <= n ; i ++){
int x;
scanf("%d",&x);
if(x == 1){
add(s,i,1ll);
add(i,s,0ll);
}
else{
add(i,t,1ll);
add(t,i,0ll);
}
}
for(int i = 1; i <= m ; i ++){
int a, b;
scanf("%d%d",&a,&b);
add(a,b,1ll);
add(b,a,1ll);
}
printf("%lld",dinic());
return 0;
}
最长不降子序列
对于问一很简单，\(n^2\) $ dp$ 即可（我居然还犹豫了一下）。由于每个点只允许选择一次，因此把一个点拆成两个，从\(<i,a>\)向\(<i,b>\)连一条容量为1的边。然后连边建图，如果 $ x_i >= x_u $且 \(dp_i = dp_u + 1\)（后一条非常重要，它决定从\(u\)到\(i\)是否存在合法转移,第一遍似这里了）就从\(<u,b>\)（已选）向\(<i,a>\)（未选）连一条边，接着对每个\(dp_i = 1\)的点，说明它可以作为一个序列的开头，所以从源点向他连边，容量为\(1\)，对每个\(dp_i = ans\)（\(ans\)是第一问答案）的点，说明它可以作为一个序列的结尾，从他向汇点连边。
然后就是喜闻乐见的最大流
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
const int M = N * N;
const int inf = 1e9;
#define ll long long
int n, m, s, t;
int head[N], nxt[M*2],to[M*2], cnt = 1; ll w[M*2], tmp[M*2];
int cur[N], dep[N], a[N],f[N]; queue<int> q;
bool vis[N];
ll maxflow;
void add(int x, int y, int z){
// printf(" %d %d %d\n",x,y,z);
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
w[cnt] = z;
to[++cnt] = x;
nxt[cnt] = head[y];
head[y] = cnt;
w[cnt] = 0;
}
bool bfs(){
for(int i = 0; i <= 2 * n + 1; i ++){
cur[i] = head[i]; vis[i] = 0; dep[i] = inf;
}
q.push(s);
dep[s] = 0;
while(!q.empty()){
int x = q.front(); q.pop();
vis[x] = 0;
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
if(dep[v] > dep[x] + 1 && w[i]){
dep[v] = dep[x] + 1;
if(!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
}
if(dep[t] != inf) return 1;
else return 0;
}
int dfs(int x, ll flow){
ll rlow = 0;
if(x == t){
maxflow += flow;
return flow;
}
ll used = 0;
for(int i = cur[x]; i; i = nxt[i]){
int v = to[i];
cur[x] = i;
if(dep[v] == dep[x] + 1 && w[i]){
if(rlow = dfs(v,min(flow - used, w[i]))){
used += rlow;
w[i] -= rlow;
w[i^1] += rlow;
if(used == flow) break;
}
}
}
return used;
}
ll dinic(){
while(bfs()){
dfs(s,inf);
}
return maxflow;
}
int q1(){
// memset(f,0x3ffffff,sizeof(f));
f[0] = 0;
int ans = 0;
for(int i = 1; i <= n ; i ++){
for(int u = 0; u < i; u ++){
if(a[i] >= a[u]){
f[i] = max(f[u] + 1,f[i]);
}
}
ans = max(ans,f[i]);
}
for(int i = 1; i <= n ; i ++){
if(f[i] == 1){
add(s, i, 1); add(i, s, 0);
}
if(f[i] == ans){
add(i + n,t,1), add(t,i + n,0);
}
for(int u = 1; u < i; u ++){
if(a[u] <= a[i] && f[i] == f[u] + 1)
add(u + n, i, 1), add(i, u + n, 0);
}
}
return ans;
}
int main(){
scanf("%d",&n);
if(n == 1){
printf("%d\n%d\n%d",1,1,1);
return 0;
}
s = 0, t = 2 * n + 1;
for(int i = 1; i <= n ; i ++){
scanf("%d",&a[i]);
add(i, i + n, 1);
}
int l = q1();
memcpy(tmp,w,sizeof(w));
printf("%d\n",l);
printf("%lld\n",dinic());
memcpy(w,tmp,sizeof(w));
add(s,1,inf);
add(1, 1 + n, inf);
if(f[n] == l){
add(n, n + n, inf);
add(n + n, t, inf);
}
maxflow = 0;
printf("%lld\n",dinic());
return 0;
}
选课
拆点的方式非常有意思
将一门课拆成\(m\)个点，分别对应\(m\)个学期。那么这就变成了一个最小割问题：用最小的代价选完所有的课。
从\((i,u - 1)\)向连边，容量为\(1\)，这样割去这条边，即代表在这学期选了这门课，可以获得相应收益。
若割去\((i,m)\)的边，显然是不合法的，那么就从\((i,m)\)向汇点连一条边权为\(inf\)的边。
若\(i\)是\(u\)的先修课，意思就是若在这个学期要学\(u\)，则最晚上个学期必须学过\(i\)，所以把\((u,j)\)向\((i,j-1)\) \((j\in [2,m])\)连一条容量为\(inf\)的边。
——最小割中的边权为\(inf\)的边，意思就是它所联通的两个点，不允许放入两个不同的集合中。
那么还剩一个问题：题中问的是最大绩点。
很简单，取任意一个值（我用的100）作为标准值，用它减去每门课的绩点，代表在这学期学完该课程的损失。
那么最小割模型就建成了，\(s\)代表的集合是选这门课，\(t\)代表的集合是不选这门课。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
bool st;
const int N = 105*105;
const int M = N*4;
const int inf = 1e9;
int n, m, k, s, t;
int head[N], nxt[M*2], to[M*2], cnt = 1;
ll w[M*2], maxflow;
int id(int x, int y){
if(!y) return s;
if(y == m + 1) return t;
return (x - 1) * m + y;
}
void add(int x, int y, int z){
// printf("%d %d %d\n",x,y,z);
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
w[cnt] = z;
to[++cnt] = x;
nxt[cnt] = head[y];
head[y] = cnt;
w[cnt] = 0;
}
struct DINIC{
int cur[N],dep[N];
bool vis[N];
queue<int> q;
bool bfs(){
for(int i = 0; i <= t; i ++){
dep[i] = inf, cur[i] = head[i], vis[i] = 0;
}
q.push(s);
dep[s] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
if(dep[v] > dep[x] + 1 && w[i]){
dep[v] = dep[x] + 1;
if(!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
}
if(dep[t] != inf) return 1;
else return 0;
}
ll dfs(int x, ll flow){
ll rlow = 0;
if(x == t){
maxflow += flow;
return flow;
}
ll used = 0;
for(int i = cur[x]; i; i = nxt[i])
{
int v = to[i];
cur[x] = i;
if(dep[v] == dep[x] + 1 && w[i]){
if(rlow = dfs(v,min(flow - used,w[i]))){
used += rlow;
w[i] -= rlow;
w[i^1] += rlow;
if(used == flow) break;
}
}
}
return used;
}
ll dinic(){
while(bfs()){
dfs(s,inf);
}
return maxflow;
}
}di;
bool ed;
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
s = 0, t = n * m + 1;
for(int i = 1; i <= n ; i++){
for(int u = 1; u <= m ; u ++){
int v; scanf("%lld",&v);
int a = id(i,u - 1), b = id(i,u);
if(v != -1) v = 100 - v;
else v = inf;
add(a,b,v);
}
add(id(i,m),t,inf);
}
for(int i = 1,a,b; i <= k; i ++){
scanf("%lld%lld",&a,&b);
for(int u = 0; u < m; u ++){
add(id(a,u),id(b,u + 1),inf);
}
}
printf("%.2lf", (double)(100.0 * n - di.dinic()) / n);
// printf("\n%.lf",abs(&ed - &st) / (1024.0 * 1024.0) );
return 0;
}
修车
这是一道费用流。
挖坑：最小费用最大流和最小割的区别在哪里？
拆点的方式和上一题非常相似。
洛谷题解给出了精髓的解释：“一个人不能两次踏进同一条河流”。
这类题的通法大概就是:对于会产生后效性（或依赖于时间）的决策，对于所处时间不同的一个点，把它拆成多个时间点上的它自己（可能有点抽象，类似频闪照片？）
注意到同一个人修同一辆车，顺序不同会导致它对答案的贡献不同。具体来说，就是若第\(i\)个人修第\(u\)辆车的时间为\(t_{i,u}\)，且这辆车是这个人修的倒数第
\(k\)辆，则它对答案的贡献为\(k*t_{i,u}\)（因为后面的人都要等待，这也就是为什么强调是倒数，正着数没有意义）。
所以我们根据这个，考虑将第\(i\)人拆成\(n\)个点，第 个点代表修倒数第\(k\)辆车的他，从这个点向第 \(u\)辆车连边，容量为\(1\)，费用为\(k*t_{i,u}\)，那么从源点向每个人（共\(n*m\)个点）连边，每辆车向汇点连边，容量为\(1\)，费用为\(0\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
const int M = N*N;
const int inf = 1e9 + 5;
#define ll long long
#define int long long
int head[N], nxt[M*2], to[M*2], cnt = 1;
ll w[M*2], s[M*2],t[N][N];
int n, m, S, T;
ll maxflow, cost;
int cur[N], dep[N];
bool vis[N];
queue<int> q;
void add(int x, int y, int z, int c){
// printf("%lld %lld %lld %lld\n",x,y,z,c);
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
w[cnt] = z;
s[cnt] = c;
to[++cnt] = x;
nxt[cnt] = head[y];
head[y] = cnt;
w[cnt] = 0;
s[cnt] = -1 * c;
}
struct COST{
bool spfa(){
for(int i = 0; i <= T; i ++){
vis[i] = 0, dep[i] = inf; cur[i] = head[i];
}
// printf("S = %lld\n",S);
q.push(S);
dep[S] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
// printf("x = %lld\n",x);
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
// printf(" v = %lld, %lld %lld %lld %lld\n",v,s[i],w[i],dep[x],dep[v]);
if(dep[v] > dep[x] + s[i] && w[i]){
dep[v] = dep[x] + s[i];
// printf(" depv = %lld\n",dep[v]);
if(!vis[v]){
// printf(" in\n");
vis[v] = 1;
q.push(v);
}
}
}
}
if(dep[T] < inf) return 1;
else return 0;
}
ll dfs(int x,ll flow){
if(x == T){
vis[T] = 1;
maxflow += flow;
return flow;
}
ll used = 0;
ll rlow = 0;
vis[x] = 1;
// printf("x = %lld\n",x);
for(int i = cur[x]; i; i = nxt[i]){
cur[x] = i;
int v = to[i];
// printf(" v = %lld\n",v);
if(dep[v] == dep[x] + s[i] && w[i] && (!vis[v] || v == T ) ){
rlow = dfs(v, min(flow - used, w[i]));
if(rlow != 0){
// printf("%lld\n",rlow);
cost += rlow * s[i];
used += rlow;
w[i] -= rlow;
w[i ^ 1] += rlow;
}
if(used == flow){
break;
}
}
}
return used;
}
ll dinic(){
while(spfa()){
// for(int i = 0; i <= T; i ++) printf("%lld ",dep[i]); printf("\n");
vis[T] = 1;
// printf("qwq\n");
while(vis[T]){
memset(vis,0,sizeof(vis));
dfs(S,inf);
// printf("p\n");
}
// exit(0);
}
return maxflow;
}
}di;
int id(int x, int y){
return x * n + y;
}
signed main(){
scanf("%lld%lld",&m,&n);
S = (m + 1) * n + 1, T = S + 1;
for(int i = 1; i <= n ; i ++){
for(int u = 1; u <= m; u ++){
scanf("%lld",&t[i][u]);
}
}
for(int i = 1; i <= n ; i ++){
for(int u = 1; u <= m; u ++){
for(int k = 1; k <= n; k ++){
add(i,id(u,k),1,k * t[i][u]);
}
}
}
// printf("qwq\n");
for(int i = 1; i <= n ; i ++) add(S,i,1,0);
for(int u = 1; u <= m; u ++){
for(int k = 1; k <= n; k ++){
add(id(u,k),T,1,0);
}
}
di.dinic();
// printf("qwq\n");
printf("%.2lf",1.0 * cost / n);
return 0;
}
奇怪游戏
感觉是一道非常好的题。
一些思路：
1.看到网格，尤其是和相邻格子相关的，考虑黑白染色，建图，白连源黑连汇，然后建图
2.“最大”“最小”可以考虑二分，但不一定要二分答案
3.判断可不可行，合不合法，可以看最大流能不能跑满，即等不等于预定的答案
那么对于这道题，棋盘格子直接黑白染色，设白格有 \(cnt_w\)个，和为\(sum_w\)，黑格有\(cnt_b\)个，和为 \(sum_b\)，那么首先，每次操作使\(sum_w\)和\(sum_b\)各加1，\(sum_w != sum_b\)肯定无解。接着设最后所有数字都变成了\(x\)，那么黑白格操作相等，一定有\(cnt_b*x - sum_b == cnt_w * x - sum_w\)，移项可得\((cnt_w - cnt_b)*x == sum_w - sum_b\)(我们钦定\(cnt_w \geq cnt_b\))。
注意这里移项的前提是\(cnt_w \neq cnt_b\)，那么对于\(cnt_w == cnt_b\)，\(x\)固定可求，用后面二分的 \(check\) 函数检查是不是正解即可。
现在讨论 \(cnt_w \neq cnt_b\) 的情况。
对于每个点\((i,u)\)，它的操作次数最多为\(x - val_{i,u}\)，那么就把它连向源或汇（根据颜色不同），容量为\(x - val_{i,u}\)，对于相邻的黑白点，从白点向黑点连边，容量\(inf\)（题目没限制任何一对相邻点的操作次数）。
然后我们建图跑最大流，\(maxflow\)即为操作次数，这是检查它是否等于\(cnt_w * x - sum_w\)即可。
还没ac，代码先咕着qwq。
文理分科
最小割好题，也是我离正解最近的一道题。
令\(s\)代表选文，\(t\)代表选理。
一个人要么选文要么选理，那么对于点\((i,u)\)，向\(s\)连边，容量为\(art\)，如果这条边被割，说明不选文，不能获得\(art\)的收益。选理同理，向\(t\)连边。
那么麻烦就在于处理“相邻的同学”。这道题没必要黑白染色哦。对每个同学，再另设两个点\((i,u,a)\)和\((i,u,b)\)，代表周围人全部选文或选理。还是以选文为例讲解，选理同理。
对每个点\((i,u,a)\)，它和它周围的四个点都向它连边，容量\(inf\)。这个点本身\(s\)连边，容量\(same_art\)。如果这条边被割，说明这五个人没有同时选文，不能获得收益。但如果这条边被选了，由于它连出的边都为\(inf\)，不可能割掉，这五个人一定同时选文。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N = 100 * 100 + 5;
const int M = N*20;
const int inf = 1e9 + 5;
int n, m, s, t;
int head[N*3], nxt[M*2], to[M*2], cnt = 1;
ll w[M*2], maxflow;
int ar[N], sc[N], sa[N], ss[N];
void add(int x, int y,int z){
// printf("%d %d %d\n",x,y,z);
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
w[cnt] = z * 1ll;
to[++cnt] = x;
nxt[cnt] = head[y];
head[y] = cnt;
w[cnt] = 0ll;
}
struct DINIC{
int dep[N*3], cur[N*3];
bool vis[N*3];
queue<int> q;
bool bfs(){
for(int i = 0; i <= t; i ++){
cur[i] = head[i], dep[i] = inf, vis[i] = 0;
}
q.push(s);
dep[s] = 0;
while(!q.empty()){
int x = q.front(); q.pop();
vis[x] = 0;
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
if(dep[v] > dep[x] + 1 && w[i]){
dep[v] = dep[x] + 1;
if(!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
}
if(dep[t] != inf) return 1;
else return 0;
}
ll dfs(int x, ll flow){
ll rlow = 0;
if(x == t){
maxflow += flow;
return flow;
}
ll used = 0;
for(int i = cur[x]; i; i = nxt[i]){
int v = to[i];
cur[x] = i;
if(dep[v] == dep[x] + 1 && w[i]){
if(rlow = dfs(v,min(flow - used,w[i]))){
used += rlow;
w[i] -= rlow;
w[i ^ 1] += rlow;
if(used == flow) break;
}
}
}
return used;
}
ll dinic(){
while(bfs()){
dfs(s,inf);
}
return maxflow;
}
}di;
int id(int x, int y){
if(x < 1 || x > n || y < 1 || y > m) return -1;
return (x - 1) * m + y;
}
void work(int a, int b){
int N = n * m;
int d = id(a,b);
add(s,d,ar[d]);
add(d,t,sc[d]);
add(d + N, d, inf);
if(id(a - 1, b) != -1) add(d + N, id(a - 1,b), inf);
if(id(a + 1, b) != -1) add(d + N, id(a + 1,b), inf);
if(id(a, b - 1) != -1) add(d + N, id(a,b - 1), inf);
if(id(a, b + 1) != -1) add(d + N, id(a,b + 1), inf);
add(s, d + N, sa[d]);
add( d,d + 2 * N, inf);
if(id(a - 1, b) != -1) add( id(a - 1,b),d + 2 * N, inf);
if(id(a + 1, b) != -1) add( id(a + 1,b),d + 2 * N, inf);
if(id(a, b - 1) != -1) add( id(a,b - 1),d + 2 * N, inf);
if(id(a, b + 1) != -1) add( id(a,b + 1),d + 2 * N, inf);
add(d + 2 * N, t , ss[d]);
}
signed main(){
scanf("%lld%lld",&n,&m);
s = 0, t = 3 * n * m + 1;
ll sum = 0;
for(int i = 1; i <= n ; i ++){
for(int u = 1; u <= m ; u ++){
scanf("%lld",&ar[id(i,u)]);
sum += ar[id(i,u)];
}
}
for(int i = 1; i <= n ; i ++){
for(int u = 1; u <= m ; u ++){
scanf("%lld",&sc[id(i,u)]);
sum += sc[id(i,u)];
}
}
for(int i = 1; i <= n ; i ++){
for(int u = 1; u <= m ; u ++){
scanf("%lld",&sa[id(i,u)]);
sum += sa[id(i,u)];
}
}
for(int i = 1; i <= n; i ++){
for(int u = 1; u <= m; u ++){
scanf("%lld",&ss[id(i,u)]);
sum += ss[id(i,u)];
}
}
for(int i = 1; i <= n ; i ++){
for(int u = 1; u <= m; u ++){
work(i,u);
}
}
// printf("%lld\n",sum);
printf("%lld",sum - di.dinic());
return 0;
}
/*
1 2
9 2
2 1
5 4
3 3
*/
无限之环
纪念一下自己用整整两个半小时ac的黑题。
同时是第一道代码没和题解的黑题。
老套路，黑白染色的费用流。
这道题有15种不同的水管，但仔细观察会发现，可以把水管的形状抽象成上下左右是否有接口。那么就可以把一个格子拆成五个点，分别表示连源汇的中心点，和上下左右四个接口。初始形状即从中心点连向四个接口，容量为\(1\)，费用为\(0\)（它不需要旋转）。注意到每次旋转一定少一个接口，再多一个接口，那就从少的这个向多的这个连边，容量\(1\)，费用\(i\)（旋转\(i\)次）（\(i\in\) \([1,2]\)）。
然后跑最小费用最大流。
如何判断无解？注意到每个接口一定都有水通过，即\(maxflow == cnt * 2\)(\(cnt\)为接口数量)。不满足该条件即无解，满足则输出\(cost\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = N*30;
const int inf = 1e9 + 5;
#define ll long long
#define id(x,y) (x-1)*m+y
#define L(x,y) id(x,y)+n*m
#define R(x,y) id(x,y)+2*n*m
#define U(x,y) id(x,y)+3*n*m
#define D(x,y) id(x,y)+4*n*m
int head[N], nxt[M*2], to[M*2], cnt = 1;
ll w[M*2], c[M*2], maxflow, cost, flows;
int n, m, s, t;
bool check(int x, int y){
return 1 <= x && x <= n && 1 <= y && y <= m;
}
void add(int x, int y, int z, int cc, int f){
if(!f) swap(x,y);
// printf("%d %d %d %d\n",x,y,z,cc);
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
w[cnt] = z;
c[cnt] = cc;
to[++cnt] = x;
nxt[cnt] = head[y];
head[y] = cnt;
w[cnt] = 0;
c[cnt] = -1 * cc;
}
struct COST{
int dep[N], cur[N];
bool vis[N];
queue<int> q;
bool spfa(){
for(int i = 0; i <= t; i ++){
dep[i] = inf, cur[i] = head[i], vis[i] = 0;
}
q.push(s); dep[s] = 0;
while(!q.empty()){
int x = q.front(); q.pop();
vis[x] = 0;
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
if(dep[v] > dep[x] + c[i] && w[i]){
dep[v] = dep[x] + c[i];
if(!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
}
if(dep[t] != inf) return 1;
else return 0;
}
ll dfs(int x, ll flow){
if(x == t) {
vis[t] = 1;
maxflow += flow;
return flow;
}
vis[x] = 1;
ll rlow = 0;
ll used = 0;
for(int i = cur[x]; i ; i = nxt[i]){
cur[x] = i;
int v = to[i];
if(dep[v] == dep[x] + c[i] && w[i] && (v == t || !vis[v])){
rlow = dfs(v,min(flow - used,w[i]));
if(rlow){
cost += rlow * c[i];
used += rlow;
w[i] -= rlow;
w[i^1] += rlow;
}
if(used == flow) break;
}
}
return used;
}
ll dinic(){
while(spfa()){
// printf("qwq\n");
vis[t] = 1;
while(vis[t]){
memset(vis,0,sizeof(vis));
// printf("p\n");
dfs(s,inf);
}
// exit(0);
}
return maxflow;
}
}di;
void work(int x, int y, int z, int f){
// printf("x = %d, y = %d, type = %d, id = %d\n",x,y,z,id(x,y) );
// int f = (id(x,y)) % 2;
// if(id(x,y) % 2 != 0) f = 1;
if(f){
if(check(x - 1,y)) add(U(x,y),D(x - 1,y),1,0,1);
if(check(x + 1,y)) add(D(x,y),U(x + 1,y),1,0,1);
if(check(x,y - 1)) add(L(x,y),R(x,y - 1),1,0,1);
if(check(x,y + 1)) add(R(x,y),L(x,y + 1),1,0,1);
}
if(f) add(s,id(x,y),inf,0,1);
else add(id(x,y),t,inf,0,1);
if(z & 1) add(id(x,y),U(x,y),1,0,f), flows ++;
if(z & 2) add(id(x,y),R(x,y),1,0,f), flows ++;
if(z & 4) add(id(x,y),D(x,y),1,0,f), flows ++;
if(z & 8) add(id(x,y),L(x,y),1,0,f), flows ++;
switch(z){
case 1 :
add(U(x,y),D(x,y),1,2,f);
add(U(x,y),L(x,y),1,1,f);
add(U(x,y),R(x,y),1,1,f);
break;
case 2 :
add(R(x,y),L(x,y),1,2,f);
add(R(x,y),U(x,y),1,1,f);
add(R(x,y),D(x,y),1,1,f);
break;
case 3 :
add(U(x,y),D(x,y),1,1,f);
add(R(x,y),L(x,y),1,1,f);
break;
case 4 :
add(D(x,y),U(x,y),1,2,f);
add(D(x,y),R(x,y),1,1,f);
add(D(x,y),L(x,y),1,1,f);
break;
case 6 :
add(R(x,y),L(x,y),1,1,f);
add(D(x,y),U(x,y),1,1,f);
break;
case 7 :
add(U(x,y),L(x,y),1,1,f);
add(R(x,y),L(x,y),1,2,f);
add(D(x,y),L(x,y),1,1,f);
break;
case 8 :
add(L(x,y),U(x,y),1,1,f);
add(L(x,y),R(x,y),1,2,f);
add(L(x,y),D(x,y),1,1,f);
break;
case 9 :
add(U(x,y),D(x,y),1,1,f);
add(L(x,y),R(x,y),1,1,f);
break;
case 11 :
add(U(x,y),D(x,y),1,2,f);
add(R(x,y),D(x,y),1,1,f);
add(L(x,y),D(x,y),1,1,f);
break;
case 12 :
add(D(x,y),U(x,y),1,1,f);
add(L(x,y),R(x,y),1,1,f);
break;
case 13 :
add(U(x,y),R(x,y),1,1,f);
add(L(x,y),R(x,y),1,2,f);
add(D(x,y),R(x,y),1,1,f);
break;
case 14 :
add(D(x,y),U(x,y),1,2,f);
add(R(x,y),U(x,y),1,1,f);
add(L(x,y),U(x,y),1,1,f);
break;
}
}
int main(){
scanf("%d%d",&n,&m);
t = 5 * (n * m) + 1;
s = 0;
// printf("%d %d\n",s,t);
// for(int i = 1; i <= n ; i ++){
// for(int u = 1; u <= m ; u ++){
// printf("%d %d %d %d %d %d %d\n",i,u,id(i,u),U(i,u),D(i,u),L(i,u),R(i,u));
// }
// }
for(int i = 1; i <= n ; i ++){
int col = i % 2;
for(int u = 1; u <= m ; u ++){
col ^= 1;
// col += 1;
int k;
scanf("%d",&k);
work(i,u,k,col);
}
}
// printf("qwq\n");
di.dinic();
// printf("%lld %lld %lld\n",flows,maxflow,cost);
// printf("%lld %lld\n",flows, maxflow);
if(maxflow * 2 < flows){
printf("-1");
}
else printf("%lld",cost);
return 0;
}
网络流总结：
一、最小割和最小费用最大流的区别？
现在来看挺智障，但既然写作业的时候很纠结这个问题，现在也就写一下。
先看作业的几道题：
最小割：善意的投票，文理分科，选课
费用流：修车，无限之环
其中可以着重对比选课和修车，因为二者很相似。
最小割有明显的划分为两个集合的思想，在选课中体现为“选”与“不选”，或者“选文”和“选理”，“睡觉”和“不睡觉”，且二者没有交集，并集一定是全集。
而费用流则没有（难不成你能不修车？），但之所以建成费用流而不是网络流，我的理解是因为它在答案最优的前提下存在一些必须满足的条件，需要先用网络流满足该条件，再用费用流使得答案最优。比如修车中每辆车必须修且仅修一次，无限之环中必须不漏水。
二、网络流技巧总结
1、黑白染色
这个应该是最常用的技巧了，看到棋盘、格子等等都可以先想一下。感觉网络流一个很大的优点就是让二维问题变得不恶心了。
2、最小割中\(inf\)的应用
上面说过了，\(inf\) 链接的两个点是不可划分到两个集合中的，可以满足题目中的一些限制，如选a必选b，某些点同时选可以获得c的收益等等……。
如果\(inf\)的边出现在网络流中，则常代表没有限制。
3、拆点技巧
拆点应该是网络流中最玄学的一个东西了。以下是我总结的几个技巧。
（1）一分为二
这个是把点权转化为边权的常用技巧，若一个点点权为a，我们常常可以考虑把它拆成两个点，中间连一条容量为a的边，再比如一个点只能选一次，则也拆成两个，中间边容量为1.
（2）频闪照片
自己瞎起的名。这种方法好像有个什么名字，太高大上了我记不住，干脆自己起个名，形象又好记。
对于会产生后效性（或依赖于时间）的决策，对于所处时间不同的一个点，把它拆成多个时间点上的它自己，然后分别处理。