【Codeforces 802C】Heidi and Library (hard)

相关链接

题目传送门:http://codeforces.com/contest/802/problem/C
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf
消圈定理:https://blog.sengxian.com/algorithms/clearcircle

解题报告

被这题强制解锁了两个新姿势qwq

  1. 上下界最小费用流:
    直接按照上下界网络流一样建图,然后正常跑费用流
  2. 带负环的费用流
    应用消圈定理,强行将负环满流

然后考完之后发现脑残了
换一种建图方法就没有负环了_(:з」∠)_

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000000;
const int M = 200;
const int INF = 1e9;

int n,k,S,T,tot,SS,TT,ans,a[M],np[M],cc[M];
int head[N],nxt[N],to[N],flow[N],cost[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int AddEdge(int u, int v, int c, int f) {
	static int E = 1;
    to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
    to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
}

class Minimum_Cost_Flow{
    int dis[N],sur[N],inq[N],vis[N]; 
    queue<int> que; 
    public:
        inline void MaxFlow() {
        	while (clearCircle()); 
            for (int ff; ff = INF, SPFA();) {
            	for (int w = TT; w != SS; w = to[sur[w]^1]) {
					ff = min(ff, flow[sur[w]]);
				}
                for (int w = TT; w != SS; w = to[sur[w]^1]) {
					flow[sur[w]] -= ff;
					flow[sur[w]^1] += ff;
				}
				ans += dis[TT] * ff;
            }
        }
    private:
        bool SPFA() {
            memset(dis,60,sizeof(dis));
            que.push(SS); dis[SS] = 0;
               
            while (!que.empty()) {
                int w = que.front(); que.pop(); inq[w] = 0;
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
                        dis[to[i]] = dis[w] + cost[i];
                        sur[to[i]] = i;
                        if (!inq[to[i]]) {
							inq[to[i]] = 1;
							que.push(to[i]);
						}
                    }
                }
            }
            return dis[TT] < INF;
        }
        bool clearCircle() {
        	memset(dis, 0, sizeof(dis));
        	memset(vis, 0, sizeof(vis));
			for (int i = 1; i <= tot; ++i) { 
   	    		if (!vis[i] && DFS(i)) {
					return 1;   
				}
			}
			return 0;
    	}
    	bool DFS(int w) {
    		vis[w] = 1;
    		if (inq[w]) {
    			int cur = w;
    			do {
					flow[sur[cur]]--;
					flow[sur[cur]^1]++;
					ans += cost[sur[cur]];
					cur = to[sur[cur]];
				} while (cur != w);
				return 1;
			} else {
    			inq[w] = 1;
				for (int i = head[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] > dis[w] + cost[i]) {
						dis[to[i]] = dis[w] + cost[i];
						sur[w] = i;
						if (DFS(to[i])) {
							inq[w] = 0;
							return 1;
						}
					}
				}
				inq[w] = 0;
				return 0;
			}
			
		}
}MCMF;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif 
	n = read(); k = read();
	S = tot = n + 4; T = n + 1;
	SS = n + 2; TT = n + 3; 
	AddEdge(T, S, 0, k); 
	AddEdge(S, 1, 0, INF);
	for (int i = 1; i <= n; i++) {
		np[i] = ++tot;
		AddEdge(np[i], i + 1, 0, INF);
		AddEdge(i, np[i], 0, INF);
		AddEdge(i, TT, 0, 1);
		AddEdge(SS, np[i], 0, 1);
		a[i] = read();
	}
	for (int i = 1; i <= n; i++) {
		cc[i] = read();
	}
	for (int i = 1; i <= n; i++) {
		ans += cc[a[i]];
		for (int j = i + 1; j <= n; j++) {
			if (a[i] == a[j]) {
				AddEdge(np[i], j, -cc[a[i]], 1);
				break;
			} 
		}
	}
	MCMF.MaxFlow();
	cout<<ans<<endl; 
	return 0;
}

【BZOJ 3577】玩手机

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3577
神犇题解:http://www.cnblogs.com/clrs97/p/4403242.html

解题报告

之前一直都是线段树优化建图
这题需要用$ST$表来优化建图

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int INF = 1e9;
const int N = 500000;
const int M = 2000000;

int S,T,E,tot,A,B,Y,X,n2[2][70][70][8]; 
int head[N],nxt[M],to[M],flow[M],n1[2][70][70];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v, int f) {
	assert(u); assert(v);
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class NetworkFlow{
	int dis[N],cur[N];
	queue<int> que;
	public:
		inline int MaxFlow() {
			int ret = 0;
			while (BFS()) {
				memcpy(cur, head, sizeof(cur));
				ret += DFS(S, INF);
			}
			return ret;
		}
	private:
		inline bool BFS() {
			memset(dis, 60, sizeof(dis));
			dis[S] = 0;
			for (que.push(S); !que.empty(); que.pop()) {
				int w = que.front();
				for (int i = head[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] > INF) {
						dis[to[i]] = dis[w] + 1;
						que.push(to[i]);
					}
				}
			}
			return dis[T] <= INF;
		}
		inline int DFS(int w, int f) {
			if (w == T) {
				return f;
			} else {
				int ret = 0;
				for (int &i = cur[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] == dis[w] + 1) {
						int tmp = DFS(to[i], min(f, flow[i]));
						ret += tmp; f -= tmp;
						flow[i] -= tmp; flow[i ^ 1] += tmp;
						if (!f) {
							break;
						}
					}
				}
				return ret;
			}
		}
}Dinic;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	X = read(); Y = read(); 
	A = read(); B = read();
	S = ++tot; T = ++tot;
	E = 1; 
	for (int i = 1; i <= X; ++i) {
		for (int j = 1; j <= Y; ++j) {
			n1[0][i][j] = ++tot;
			n1[1][i][j] = ++tot;
			AddEdge(n1[0][i][j], n1[1][i][j], read());
		}
	}
	for (int i = X; i; --i) {
		for (int j = Y; j; --j) {
			for (int a = 0, len = 1; i + len - 1 <= X && j + len - 1 <= Y; ++a, len <<= 1) {
				n2[0][i][j][a] = ++tot;
				n2[1][i][j][a] = ++tot;
				if (!a) {
					AddEdge(n2[0][i][j][a], n1[0][i][j], INF);
					AddEdge(n1[1][i][j], n2[1][i][j][a], INF);	
				} else {
					int llen = len >> 1;
					AddEdge(n2[0][i][j][a], n2[0][i][j][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i + llen][j][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i][j + llen][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i + llen][j + llen][a - 1], INF);
					
					AddEdge(n2[1][i][j][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i][j + llen][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i + llen][j][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i + llen][j + llen][a - 1], n2[1][i][j][a], INF);
				} 
			}	
		}
	}
	for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= A; ++i) {
		p0 = ++tot; p1 = ++tot;
		w = read(); 
		x1 = read(); y1 = read();
		x2 = read(); y2 = read();
		AddEdge(S, p0, INF);
		AddEdge(p0, p1, w);
		
		int len = x2 - x1 + 1, lg = 0, d = 1;
		for (; (d << 1) <= len; lg++, d <<= 1);
		AddEdge(p1, n2[0][x1][y1][lg], INF);
		AddEdge(p1, n2[0][x1][y2 - d + 1][lg], INF);
		AddEdge(p1, n2[0][x2 - d + 1][y1][lg], INF);
		AddEdge(p1, n2[0][x2 - d + 1][y2 - d + 1][lg], INF);
	}
	for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= B; ++i) {
		p0 = ++tot;	p1 = ++tot;
		w = read();
		x1 = read(); y1 = read();
		x2 = read(); y2 = read();
		AddEdge(p0, p1, w);
		AddEdge(p1, T, INF);
		
		int len = x2 - x1 + 1, lg = 0, d = 1;
		for (; (d << 1) <= len; lg++, d <<= 1);
		AddEdge(n2[1][x1][y1][lg], p0, INF);
		AddEdge(n2[1][x1][y2 - d + 1][lg], p0, INF);
		AddEdge(n2[1][x2 - d + 1][y1][lg], p0, INF);
		AddEdge(n2[1][x2 - d + 1][y2 - d + 1][lg], p0, INF);
	}
	assert(tot < N);
	assert(E < M);
	printf("%d\n", Dinic.MaxFlow());
	return 0;
}

【CodeChef DINING】[January Cook-off 2014] Dining

相关链接

题目传送门:https://www.codechef.com/problems/DINING
官方题解:https://discuss.codechef.com/questions/70332/dining-editorial

解题报告

这题套路啊,神™套路啊!

关键问题是它的概率是乘起来的,不是加起来
于是很多东西都不能用啊!
于是题解说我们可以取对数,因为$\log(a \cdot b) = \log (a) + \log (b)$
于是就变成了加法,于是就可以跑一个费用流了

把乘法换搞成加法,在模意义下还有一种做法,参见:

【BZOJ 3992】[SDOI2015] 序列统计

【HDU 5772】String problem

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5772
神犇题解:http://www.cnblogs.com/qscqesze/p/5715939.html

解题报告

日常看错题系列:

  1. 子序列看成子串
  2. 值域范围$0 \sim 9$看漏

于是只会跑$n$遍网络流的算法了 QwQ
大概就是枚举左端点,然后暴力跑

考虑原题的话,唯一的Trick就是如何处理一个数第一次选的代价不同
我们可以使用最大权闭合子图来解决这个问题:

每一类数字新建一个结点,权值为$b_i – a_i$
值为该数字的所有序列上的点向这个新建的点连一条有向边

至于本题的其他部分就没什么好玩的了

【BZOJ 1937】[SHOI2004] Mst最小生成树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1937
神犇题解:https://blog.sengxian.com/solutions/bzoj-1937

解题报告

我们首先可以得到一个结论:$T$中的边的边权只会减少,其他边的边权只会增加
于是我们将$T$中的边放在左边,其他边放在右边,都作为二分图的点,点权为边权
然后左右两两连边,边权$v_i$为右边点的权值减左边点的权值

此时问题转化为,每一个点设一个$d_i$,满足二分图中任意一条边$i \to j$满足$v_{i \to j} \le d_i + d_j$,求最小化$\sum{d_i}$
这是$KM$算法的关键步骤。于是直接上$KM$算法就可以了

但我不会$KM$算法
←为什么这个频率这个鬼畜啊 QwQ

但不会$KM$算法我们也能做,回忆$KM$算法顶标的作用
最小的顶标和就是最大权匹配的权值和
于是我们用费用流增广这个二分图,直到增广到权值为负就可以了

【CodeChef PARADE】Annual Parade

相关链接

题目传送门:https://www.codechef.com/problems/PARADE
神犇题解:http://blog.csdn.net/jasonvictoryan/article/details/53395098

解题报告

这题先只考虑一个询问的情况

这显然可以使用拆点+二分图最大权匹配去做
具体来说:每个点拆成出度和入度两个点,然后出度放左边,入度放右边
考虑每找到一条增广路,就是在原图中走了一条边
那么不管是连接了两条路径,或是新走到一个点,都会使总费用减少一个$C$
但每走一次增广路,都会花费一些费用$v$
显然我们应该在$v > C$的时候停止增广

现在考虑多个询问
因为是费用流算法,所以单次增广的费用$v_i$是单调不减的
于是我们可以记录每一次增广的$v_i$。对于询问就二分,然后求前缀和就好
当然不想二分,也可以先排个序然后扫一遍,反正总的时间复杂度主要还是卡在费用流那里

【BZOJ 2521】[SHOI2010] 最小生成树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2521
神犇题解:http://krydom.com/bzoj2521/

解题报告

这题有一个非常显然的贪心:做Kruskal的时候,如果会使那条边的两个端点连在一起就暴力加权值
但这样显然也是错误的,因为我们可能是在之前的步骤就废掉一些边
于是怎么解决这个问题呢?
我们相当于不能在某两个端点之间有通路,那么这和网络流的增广路相同
于是我们把边的容量设为暴力改的时候需要的花费,然后跑一遍最小割就可以了

【日常小测】cut

题目大意

给定一个$n(n \le 100)$个点的连通图
不同顶点之间有$n^2$个最小割
现在给定这$n^2$个最小割,让你构造一个图使其满足条件

解题报告

据说这是论文题?

因为任意两点间的最小割可以用最小割树来表示
所以我们考虑构造一个树形结构

因为一条路径上的最小割相当于取$min$,所以流量大的不会影响流量小的
所以我们先按边权从大到小排序
如果当前这条边的两个端点已经在一个连通块内,那么暴力判断是否符合要求
如果不在一个块内,那么连一条边

至于为什么这样是对的,因为已经按权值排序了
如果不在一个连通块内,还不连边,那么最终连通这两块的权值一定大于要求的最小割,所以必须立刻连边
至于已经连边了还冲突的话,因为之前的边都是必要的,所以也没有调整的需要,一定是无解的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 109;
const int M = N * N << 1;
const int INF = 1e9;
 
int n,tot,head[N],nxt[M],to[M],cost[M],fa[N];
struct Data{
    int u,v,val;
    inline Data() {}
    inline Data(int a, int b, int c):u(a),v(b),val(c) {}
    inline bool operator < (const Data &B) const {
        return val > B.val;
    }
}p[N*N*N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline void AddEdge(int u, int v, int c) {
    static int E = 1; cost[E+1] = cost[E+2] = c; 
    to[++E] = v; nxt[E] = head[u]; head[u] = E;
    to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
 
int cal(int w, int f, int pur, int mn) {
    if (w == pur) return mn;
    for (int i=head[w],tmp;i;i=nxt[i]) {
        if (to[i] != f) {
            tmp = cal(to[i], w, pur, min(mn, cost[i]));
            if (~tmp) return tmp;
        }
    } return -1;
}
 
int find(int x) {return x==fa[x]? x: fa[x]=find(fa[x]);}
 
int main() {
    n = read();
    for (int i=1,v;i<=n;i++) {
        fa[i] = i;
        for (int j=1;j<=n;j++) {
            if (v=read(), i==j) continue;
            p[++tot] = Data(i, j, v);   
        }
    }
    sort(p+1, p+1+tot);
    for (int i=1;i<=tot;i++) {
        int u=p[i].u, v=p[i].v, val=p[i].val;
        if (find(u) == find(v)) {if(cal(u,u,v,INF)!=val)cout<<-1,exit(0);}
        else fa[find(u)] = fa[v], AddEdge(u, v, val);
    }
    cout<<n-1<<endl;
    for (int i=2;to[i];i+=2) printf("%d %d %d\n",to[i],to[i+1],cost[i]);
    return 0;
}

【LA 5928】[2016-2017 ACM-ICPC CHINA-Final] Mr.Panda and TubeMaster

相关链接

题目传送门:https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=769&page=show_problem&problem=5928

中文题面

Mr. Panda很喜欢玩游戏。最近,他沉迷在一款叫Tube Master的游戏中。
在Tube Master游戏中,玩家可以在$N\times M (N,M \le 30)$的网格中放置管道。每个网格要么为空格子,要么放置下面四种管子中的一种。

当两个相邻(有公共边的格子视为相邻)的格子中间有管道连接(例如下面这幅图),那么玩家将会得到一些分数(具体细节将在输入描述中给出)。

游戏中,有些格子是关键格子。对于每一个关键格子,玩家必须放置这四种管道中的任意一种,不得留空,否则玩家将输掉整局游戏。
玩家放好管道后,这个$N\times M$的网格必须满足以下两个条件,否则玩家将输掉整局游戏。
1. 每个格子要么没有管道,要么这个格子的管道是环形管道的一部分。
2. 每个关键格子必须放置管道。
特别地,如果没有关键格子,那么空网格也是一组合法解。
可以有多个环。

在上面三张图中,灰色格子是关键格子。其中:
左边的图不合法,因为关键格子没有放管道。
中间的图合法。
右边的图不合法,因为管道没有构成环。
Mr. Panda想要打赢这局游戏并且拿到尽可能多的分数。你能帮他计算他最多能拿多少分吗?

解题报告

这是一道非常玄妙的费用流题目

我们先将所有的点黑白染色
然后我们钦定黑点是从横变竖,白点是从竖变横(如果刚好相反的话,我们把这个环给反向就可以了)
之后我们再把每个点拆成入度和出度两个点,入度全部放左边,出度放右边
根据我们的旨意,黑色的入度只能匹配其上下的方格的出度,其出度只能匹配其左右两个方格的入度
我们在连边的时候,注意这个限制。
根据这个题目的启示TopCoder – Curvy on Rails,如果存在完备匹配,这个匹配的意义一定是几个圈

现在唯一的问题就是,有一些点可以不选了
那么我们可以认为他的出度与自己的入度匹配了(自环)
于是对于不必选的点我们连一条自己到自己的边,必选的边不连
之后搞一发费用流就可以了!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000;
const int M = 100000;
const int INF = 1e9;

int n,m,S,T,E,head[N],nxt[M],cost[M],flow[M],to[M];
int pos[30][30],cx[30][30],cy[30][30],vis[30][30];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int AddEdge(int u, int v, int c, int f) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
	return E - 1;
}

class Minimum_Cost_Flow{
    int dis[N],sur[N],inq[N];
    queue<int> que; 
    public:
        inline int MaxFlow() {
            int ret_cost = 0, ret_flow = 0;
            for (int f=INF,w;SPFA();f=INF) {
                for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
                for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
                ret_cost += dis[T] * f;
                ret_flow += f;
            }
            return ret_flow == n * m? ret_cost: -INF;
        }
    private:
        bool SPFA() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
              
            while (!que.empty()) {
                int w = que.front(); que.pop(); inq[w] = 0;
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
                        dis[to[i]] = dis[w] + cost[i];
                        sur[to[i]] = i;
                        if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
}MCMF;

inline int id(int x, int y, int t) {
	return ((y - 1) * n + x - 1) * 2 + t;
}

int main() {
	for (int TT=read(),t=1;t<=TT;t++) {
		S = 0; T = N - 1; E = 1; memset(head,0,sizeof(head));
		printf("Case #%d: ",t);	m = read(); n = read();
		for (int j=1,v;j<=m;j++) for (int i=1;i<n;i++) cx[i][j] = -read();
		for (int j=1,v;j<m;j++) for (int i=1;i<=n;i++) cy[i][j] = -read();
		for (int e=read(),x,y;e;e--) x=read(), y=read(), vis[y][x] = t;
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++) {
				AddEdge(S, id(i,j,1), 0, 1);
				AddEdge(id(i,j,2), T, 0, 1);
				if (vis[i][j] != t) AddEdge(id(i,j,1), id(i,j,2), 0, 1); 
			}
		}
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++) {
				if ((i + j) & 1) {
					if (i < n) AddEdge(id(i+1,j,1), id(i,j,2), cx[i][j], 1);
					if (i > 1) AddEdge(id(i-1,j,1), id(i,j,2), cx[i-1][j], 1);
					if (j < m) AddEdge(id(i,j,1), id(i,j+1,2), cy[i][j], 1);
					if (j > 1) AddEdge(id(i,j,1), id(i,j-1,2), cy[i][j-1], 1);
				} 
			}
		}
		int tmp = MCMF.MaxFlow();
		if (tmp == -INF) puts("Impossible");
		else printf("%d\n",-tmp);
	}
	return 0;
}

—————————— UPD 2017.3.22 ——————————
Claris给我讲了一点新的姿势,不需要原来的无源汇带上下界费用流了
只需要一个普通的费用流即可,已经更新
Claris真是太强了 _(:з」∠)_

【BZOJ 3638】[CF172] k-Maximum Subsequence Sum

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3638
神犇题解Ⅰ:http://blog.csdn.net/werkeytom_ftd/article/details/50950623
神犇题解Ⅱ:http://hzwer.com/6715.html

解题报告

这题非常的妙啊!
但我还是点亮手动增广这个技能点 QwQ

考虑单次询问整个区间,我们建一个费用流的图就可以辣!
然后我们发现这个费用流的每次增广相当于区间取反+区间询问最大连续字段和
这个是线段树的经典问题,于是我们用线段树来模拟增广的过程就可以辣!

【日常小测】摩尔庄园

题目大意

给定一棵$n(n \le 10^5)$个节点的以$1$为根的有根树,第$i$个结点上有$c_i$个食物,其父亲为$\lfloor \frac{i}{2} \rfloor$
现在依次给出$m$个拉姆,依次询问前$i$个拉姆都有东西吃的最短移动距离和
依次输出这$m$次询问的答案

解题报告

如果点数很小的话,我们显然可以跑个费用流就可以了!
但这题点这么多怎么办 QwQ

那我们就手动增广!
考虑维护一个$val_i$表示以$i$为根的子树中最近的有食物的点到$i$的距离
于是我们可以花$O(\log n)$的时间暴力在树上爬一爬就可以代替费用流的SPFA
然后考虑修改沿途边的边权,因为树高是$\log n$级别的,于是我们也是暴力修改就好
最后再用更新一下受影响的$val_i$来方便下次增广就可以辣!

以前听说过手动增广的题目,不过一次都还没有写过
这次写一写感觉这货非常好玩啊!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100009;
const int INF = 1e9;
 
int  n,m,vout,cnt[N],pos[N];
int sur[N],val[N],cost[N]; 
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline int LCA(int u, int v) {
    for (;u!=v;u>>=1) 
        if (u < v) swap(u, v);
    return u;
}
 
inline void update(int w) {
    static int ls, rs, cl, cr;
    if (cnt[w]) sur[w] = w, val[w] = 0;
    else sur[w] = 0, val[w] = INF;
    if ((ls=w<<1) <= n) {
        cl = cost[ls] > 0? -1: 1;
        if(val[ls] + cl < val[w]) {
            val[w] = val[ls] + cl;
            sur[w] = sur[ls];
        }
    }
    if ((rs=ls|1) <= n) {
        int cr = cost[rs] > 0? -1: 1;
        if(val[rs] + cr < val[w]) {
            val[w] = val[rs] + cr;
            sur[w] = sur[rs];
        }
    }
}
 
inline void modify(int w, int p, int delta) {
    while (w != p) {
        cost[w] += delta;
        update(w); w >>= 1;  
    }
}
 
inline int query(int w, int &ans) {
    static int ret, delta; delta = 0;
    for (;w;w>>=1) {
        if (val[w] + delta < ans) {
            ans = val[w] + delta;
            ret = sur[w];
        }
        delta += cost[w] >= 0? 1: -1;
    } return ret;
}
 
int main() {
    n = read(); m = read();
    for (int i=1;i<=n;i++) cnt[i] = read();
    for (int i=1;i<=m;i++) pos[i] = read();
    for (int i=n;i;i--) update(i);
    for (int i=1,u,v,ans=INF;i<=m;++i,ans=INF) {
        cnt[v=query(u=pos[i], ans)]--; 
        printf("%d\n",vout+=ans);
        int lca = LCA(u, v);
        modify(u, lca, 1); modify(v, lca, -1);
        for (;lca;lca>>=1) update(lca);
    }
    return 0;
}

【Yandex Contest 3529D】[NEERC 2016] Delight for a Cat

相关链接

题目传送门:https://contest.yandex.ru/neerc2016/contest/3529/problems/D/
敦敦敦题解:https://oi.qizy.tech/wp-content/uploads/2017/03/delight_for_a_cat_solution.pdf

一句话题意

有$n$天,每天只能睡觉或者吃饭,每天睡觉和吃饭的收益不同
要求连续$k$天中,至少有$ms$天睡觉,$me$天吃饭
求最大收益

解题报告

这题之前在绍一集训的时候考过
但当时并没有改题 QwQ
话说根据方程建费用流这个技能始终没在科技树上点亮啊

正解的话,其实也不难,就是瞎推一推式子
然后可以得到一个和志愿者招募那个题差不多的式子
于是我们撸一发费用流就可以啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1009;
const int M = 5000;
const LL INF = 1e18;

int head[N],to[M],nxt[M],cost[M],flow[M];
int n,k,me,ms,S,T,s[N],e[N],edge[N];
LL vout,dis[N];

inline int Add_Edge(int u, int v, int f, int c) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
	return E - 1;
}

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Minimum_Cost_Flow{
    int sur[N],inq[N];
    queue<int> que;
    public:
        inline LL MaxFlow() {
            LL ret_cost = 0;
            for (int f=1e9,w;SPFA();f=1e9) {
                for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
                for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
                ret_cost += dis[T] * f; 
            }
            return ret_cost;
        }
    private:
        bool SPFA() {
            fill(dis, dis+N, INF);
            que.push(S); dis[S] = 0;
              
            while (!que.empty()) {
                int w = que.front(); que.pop(); inq[w] = 0; 
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
                        dis[to[i]] = dis[w] + cost[i];
                        sur[to[i]] = i;
                        if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
}MCMF;

int main() {
	S = 0; T = N - 1;
	n = read(); k = read();
	ms = read(); me = read();
	for (int i=1;i<=n;i++) vout += (s[i] = read());
	for (int i=1;i<=n;i++) e[i] = read();
	Add_Edge(S, n-k+2, k-ms, 0);
	Add_Edge(1, T, k-ms, 0); 
	for (int i=2;i<=n-k+2;i++) Add_Edge(i, i-1, k-ms-me, 0);
	for (int i=1;i<=n;i++) edge[i] = Add_Edge(min(i+1, n-k+2), max(1, i-k+1), 1, s[i] - e[i]);
	printf("%lld\n",vout-MCMF.MaxFlow());
	for (int i=1;i<=n;i++) putchar(flow[edge[i]]? 'S': 'E');
	return 0;
}

【TopCoder SRM558】Surrounding Game

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/01/SurroundingGame.html
中文题面:http://www.cnblogs.com/enigma-aw/p/6236241.html
神犇题解:http://vfleaking.blog.163.com/blog/static/17480763420129289015251/

解题报告

看到这种收益相关的题目,肯定想到最小割
并且对于这题来讲,不难想到下面这种构图方式:

$ j$ 是点 $ i$ 拆出来的点, $ a$ 、 $ b$ 、 $ c$ 、 $ d$ 是与i点相邻的点拆出来的点

但这样构图,节点的意义不具备普遍性,即对于考虑的关系不同,相同节点的意义不同

比如对于点j,现在的图中不能存在 $ j \to T$ 这条边,但在考虑其他点的时候,该边不可被忽略

因为是网格图,所以考虑能否使用二分图染色解决这个问题
考虑将黑点连到 $ S$, 白点连到 $ T$
并规定,黑点被割到 $ S$ 集表示选,白点被割到 $ S$ 集表示不选(割到 $ T$ 集的意义以此递推)

于是提到的第一种建图方式就可以得到下面这种建图方式:

然后我们惊奇地发现,该种建图方式满足原题的一切要求!

不要问我是怎么推出来的
我也普吉岛…

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000;
const int M = 100000;
const int INF = 1e9;

int S,T,head[N],nxt[M],to[M],flow[M];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1,0};

class Network_Flow{
    int cur[N],dis[N];
    queue<int> que;
    public:
        inline int MaxFlow() {
            int ret = 0;
            while (BFS()) {
                memcpy(cur, head, sizeof(head));
                ret += DFS(S, INF);
            }   
            return ret;
        }
    private:
        inline bool BFS() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
                 
            while (!que.empty()) {
                int w = que.front(); que.pop();
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > INF && flow[i]) {
                        dis[to[i]] = dis[w] + 1;
                        que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
        int DFS(int w, int f) {
            if (w == T) return f;
            else {
                int ret = 0;
                for (int tmp,&i=cur[w];i;i=nxt[i]) {
                    if (dis[to[i]] == dis[w] + 1 && flow[i]) {
                        tmp = DFS(to[i], min(f, flow[i])); 
                        flow[i] -= tmp; flow[i^1] += tmp;
                        f -= tmp; ret += tmp;
                        if (!f) break;
                    }
                }
                return ret;
            }
        }
}Dinic;

class SurroundingGame {
	int n,m,E,vout; 
    public:
    	int maxScore(vector<string> cost, vector<string> benefit) {
    	    init();
			m = cost.size();
    	    n = cost[0].size();
    	    for (int j=0;j<m;j++) {
				for (int i=0;i<n;i++) {
					vout += Val(benefit[j][i]);
				}
			}
    	    for (int j=1;j<=m;j++) {
				for (int i=1;i<=n;i++) {
					if (i + j & 1) {
						Add_Edge(S, id(i,j,1), Val(cost[j-1][i-1]));
						Add_Edge(id(i,j,1), id(i,j,2), Val(benefit[j-1][i-1]));
						for (int k=1,x,y;k<=4;k++) {
							x = i + dx[k];
							y = j + dy[k];
							if (1 <= x && x <= n && 1 <= y && y <= m) {
								Add_Edge(id(i,j,1), id(x,y,2));
								Add_Edge(id(i,j,2), id(x,y,1));
							}  
						}
					} else {
						Add_Edge(id(i,j,1), T, Val(cost[j-1][i-1]));
						Add_Edge(id(i,j,2), id(i,j,1), Val(benefit[j-1][i-1]));
					}	
				}
			}
			return vout - Dinic.MaxFlow();
   		}
   	private:
   		inline void init() {
			E = 1; S = vout = 0; T = N - 1;
			memset(head,0,sizeof(head));   
		}
		inline void Add_Edge(int u, int v, int f = INF) {
			to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
			to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
		} 
		inline int id(int x, int y, int t) {
			return ((y-1) * n + (x-1)) * 2 + t;
		}
		inline int Val(char c) {
			if ('A' <= c && c <= 'Z') return c - 29;
			if ('a' <= c && c <= 'z') return c - 87;
			if ('0' <= c && c <= '9') return c - 48;
		}
};

【TopCoder SRM570】Curvy on Rails

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=12432
中文题面:http://www.cnblogs.com/enigma-aw/p/6237246.html
神犇题解:http://metthesoul.blog.163.com/blog/static/23032003620147269343401/

解题报告

首先考虑一个简单的子问题:

给定你一个网格图,其中有一些点有障碍,不能经过
问:能否通过一些回路,使得每一个点恰好经过一次

考虑回路的性质:

  1. 回路中的每一个点的度一定是 $ 2$
  2. 如果每一个点的度都是 $ 2$ ,那么这一定是由一些回路构成的图

这样的话,这个 $ Subcase$ 就可以通过染色后二分图匹配来解决了

现在回到原问题,显然可行解的判断可以用上述算法来解决
现在来考虑 towns with Curvies

在上一个 $ Subcase$ 中使用的二分图匹配,实际上是对 进行匹配
现在考虑将度分类:

  1. 横向的度
  2. 纵向的度

对于 towns with Curvies 来说:如果同类的度匹配,那么就得付出代价
于是考虑将每一个点拆成一个横向的度和纵向的度
然后原图中相邻的格子,只连对应的点(纵向相邻就只连代表纵向的点)
这样的话,如果存在完备匹配,那么一定是一个两个不同类的度匹配

现在再来考虑付出代价的情况:
将二分图匹配改造成费用流,已建的边费用全部为 $ 0$
然后在同一个格子拆开的点之间连一条双向、流量为 $ 1$、费用为 $ 0$ 的边
这样的话,就相当于两个匹配都使用同一类度的时候得付出 $ 1$ 的代价

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int L = 30;
const int N = 2000;
const int M = 50000;
const int INF = 1000000000;

int S,T,head[N],nxt[M],to[M],flow[M],cost[M];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};

class Minimum_Cost_Flow{
    int dis[N],sur[N],inq[N];
    queue<int> que;
    public:
        inline pair<int,int> MaxFlow() {
        	int ret_cost = 0, ret_flow = 0;
            for (int f=INF,w;SPFA();f=INF) {
                for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
                for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
                ret_cost += dis[T] * f;
                ret_flow += f;
            }
            return make_pair(ret_cost, ret_flow);
        }
    private:
        bool SPFA() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
             
            while (!que.empty()) {
                int w = que.front(); que.pop(); inq[w] = 0;
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
                        dis[to[i]] = dis[w] + cost[i];
                        sur[to[i]] = i;
                        if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
}MCMF;

class CurvyonRails {
	int n,m,cnt,E;
	char pat[L][L];
    public:
    	int getmin(vector<string> field) {
    	    init();
    	    m = field.size();
    	    n = field[0].size();
    	    for (int j=0;j<m;j++) {
				for (int i=0;i<n;i++) {
					pat[i+1][j+1] = field[j][i];
				}
			}
			for (int j=1;j<=m;j++) {
				for (int i=1;i<=n;i++) {
					if (pat[i][j] == 'w') continue;
					else {
						if (++cnt, i + j & 1) {
							Add_Edge(id(i,j,0), T, 1);
							Add_Edge(id(i,j,1), T, 1);
						} else {
							Add_Edge(S, id(i,j,0), 1);
							Add_Edge(S, id(i,j,1), 1);
							for (int k=1,x,y;k<=4;k++) {
								x = i + dx[k];
								y = j + dy[k];
								if (1 <= x && x <= n && 1 <= y && y <= m) {
									if (x == i) Add_Edge(id(i,j,1), id(x,y,1), 1);
									if (y == j) Add_Edge(id(i,j,0), id(x,y,0), 1);
								}
							}
						}
						if (pat[i][j] == '.') {
							Add_Edge(id(i,j,0), id(i,j,1), 1);
							Add_Edge(id(i,j,1), id(i,j,0), 1);
						}
						if (pat[i][j] == 'C') {
							Add_Edge(id(i,j,0), id(i,j,1), 1, 1);
							Add_Edge(id(i,j,1), id(i,j,0), 1, 1);
						}
					}
				}
			}
			pair<int,int> vout = MCMF.MaxFlow();
			if (vout.second < cnt) return -1;
			else return vout.first;
   		}
   	private:
   		inline int id(int x, int y, int t) {
			return ((y-1)*n + (x-1)) * 2 + 1 + t;   
		}
   		inline void init() {
			E = 1; S = cnt = 0; T = N - 1;
			memset(head,0,sizeof(head));   	
		}
   		inline void Add_Edge(int u, int v, int f, int c = 0) {
			to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
			to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
		}
};

【BZOJ 3144】[HNOI2013] 切糕

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3144
神犇题解:http://www.cnblogs.com/zig-zag/archive/2013/05/13/3076563.html

解题报告

这题根据阶段来建图应该是非常经典的建图方式
考虑每一个纵轴,上端连T,下端连S
这样的话,最后在S集合中的点等价于在斜面下方
而在T集合中的点等价于在斜面上方
考虑D的限制,连两条容量为INF的边就好啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 70000;
const int M = N << 2;
const int INF = 1e9;

int p,q,r,d,S,T,head[N],nxt[M],to[M],flow[M];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

inline void Add_Edge(int u, int v, int f = INF) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int id(int x, int y, int z) {
	return ((y - 1) * q + x - 1) * (r + 1) + z;
}

class Network_Flow{
    int cur[N],dis[N];
    queue<int> que;
    public:
        inline int MaxFlow() {
            int ret = 0;
            while (BFS()) {
                memcpy(cur, head, sizeof(head));
                ret += DFS(S, INF);
            }   
            return ret;
        }
    private:
        inline bool BFS() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
               
            while (!que.empty()) {
                int w = que.front(); que.pop();
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > INF && flow[i]) {
                        dis[to[i]] = dis[w] + 1;
                        que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
        int DFS(int w, int f) {
            if (w == T) return f;
            else {
                int ret = 0;
                for (int tmp,&i=cur[w];i;i=nxt[i]) {
                    if (dis[to[i]] == dis[w] + 1 && flow[i]) {
                        tmp = DFS(to[i], min(f, flow[i])); 
                        flow[i] -= tmp; flow[i^1] += tmp;
                        f -= tmp; ret += tmp;
                        if (!f) break;
                    }
                }
                return ret;
            }
        }
}Dinic;

int main() {
	p = read(); q = read();
	r = read(); d = read();
	S = 0; T = N - 1;
	for (int z=1;z<=r;z++) {
		for (int y=1;y<=p;y++) {
			for (int x=1,v;x<=q;x++) {
				Add_Edge(id(x,y,z), id(x,y,z+1), read());
				for (int k=0,X,Y;k<4;k++) {
					X = x + dx[k];
					Y = y + dy[k];
					if (1 <= X && X <= q && 1 <= Y && Y <= p) {	
						if (z > d) Add_Edge(id(x,y,z), id(X,Y,z-d));
						if (z+d+1 <= r) Add_Edge(id(X,Y,z+d+1), id(x,y,z));
					}
				}
			}
		}
	}
	for (int x=1;x<=q;x++) {
		for (int y=1;y<=p;y++) {
			Add_Edge(S, id(x,y,1));
			Add_Edge(id(x,y,r+1), T);
		}
	}
	printf("%d\n",Dinic.MaxFlow());
	return 0;
}

【BZOJ 3894】文理分科

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3894
神犇题解:http://blog.csdn.net/popoqqq/article/details/43968017

解题报告

如果“同选文或同选理”这种有加成的关系只局限于两个人之间
那大家肯定都会,建图方法如下:

但这题有加成的关系不限于两点之间,而是五点之间
似乎没法做了,但让我们来考虑最小割的意义:

最后将原图划分为两个集合:S集 & T集

于是我们不妨设最后在S集的点选文,T集的点选理
这样的话,考虑选文的点需要花费多少费用:

  1. 选理的费用
  2. 同选理的费用

第一个很好解决,向T直接边就好
第二个因为涉及5个点,于是只能新建 关键点 再从 关键点 连向汇点
酱紫的话,似乎就非常好理解了?

现在再重新考虑之前提到的仅限于两点间的加成的情况
似乎也可以这样来建图,似乎只是边数和点数多了一点:

再仔细想一想的话,似乎只是把可以合并的边给合并掉了?

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 30000+9;
const int M = 300000+9; 
const int INF = 1e9;

int n,m,S,T,head[N],to[M],nxt[M],flow[M];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1},vout;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int f = INF) {
	static int T = 1;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = f;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = 0;
}

inline int id(int x, int y, int t) {
	return n * m * (t - 1) + (y - 1) * n + x;
}

class MaxFlow{
	int cur[N],dis[N];
	queue<int> que;
	public:
		inline int solve() {
			int ret = 0;
			while (BFS()) {
				memcpy(cur, head, sizeof(head));
				ret += DFS(S, INF);
			}	
			return ret;
		}
	private:
		inline bool BFS() {
			memset(dis,60,sizeof(dis));
			que.push(S); dis[S] = 0;
			
			while (!que.empty()) {
				int w = que.front(); que.pop();
				for (int i=head[w];i;i=nxt[i]) {
					if (dis[to[i]] > INF && flow[i]) {
						dis[to[i]] = dis[w] + 1;
						que.push(to[i]);
					}
				}
			}
			return dis[T] < INF;
		}
		int DFS(int w, int f) {
			if (w == T) return f;
			else {
				int ret = 0;
				for (int tmp,&i=cur[w];i;i=nxt[i]) {
					if (dis[to[i]] == dis[w] + 1 && flow[i]) {
						tmp = DFS(to[i], min(f, flow[i])); 
						flow[i] -= tmp; flow[i^1] += tmp;
						f -= tmp; ret += tmp;
						if (!f) break;
					}
				}
				return ret;
			}
		}
}Dinic;

int main() {
	m = read(); n = read();
	S = 0; T = N - 1;
	for (int j=1,tmp;j<=m;j++) 
		for (int i=1;i<=n;i++)
			vout += (tmp = read()), 
			Add_Edge(id(i,j,1), T, tmp);
	for (int j=1,tmp;j<=m;j++) 
		for (int i=1;i<=n;i++)
			vout += (tmp = read()), 
			Add_Edge(S, id(i,j,1), tmp);
	for (int j=1,tmp;j<=m;j++)
		for (int i=1;i<=n;i++)
			vout += (tmp = read()), 
			Add_Edge(id(i,j,3), T, tmp);
	for (int j=1,tmp;j<=m;j++)
		for (int i=1;i<=n;i++)
			vout += (tmp = read()), 
			Add_Edge(S, id(i,j,2), tmp);
	for (int j=1,w=0;j<=m;j++) {
		for (int i=1;i<=n;i++) {
			Add_Edge(id(i,j,1), id(i,j,1));
			Add_Edge(id(i,j,2), id(i,j,1));
			Add_Edge(id(i,j,1), id(i,j,3));
			for (int k=0,x,y;k<4;k++) {
				x = i + dx[k];
				y = j + dy[k];
				if (1 <= x && x <= n && 1 <= y && y <= m) {
					Add_Edge(id(i,j,2), id(x,y,1));
					Add_Edge(id(x,y,1), id(i,j,3));
				}
			}
		}
	}
	printf("%d\n",vout-Dinic.solve());
	return 0;
}