最小割 – Qizy's Database

【HDU 5772】String problem

2017年4月3日2017年7月21日 Qizy 2 Comments

解题报告

日常看错题系列：

子序列看成子串

值域范围$0 \sim 9$看漏

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

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

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

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

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

2017年3月25日2017年3月25日 Qizy 16 Comments

解题报告

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

【日常小测】cut

2017年3月22日2017年3月22日 Qizy 21 Comments

题目大意

给定一个$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;
}

【TopCoder SRM558】Surrounding Game

2017年1月3日2017年1月3日 Qizy 85 Comments

解题报告

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

$ 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;
		}
};

【BZOJ 3144】[HNOI2013] 切糕

2016年12月28日2016年12月28日 Qizy 266 Comments

解题报告

这题根据阶段来建图应该是非常经典的建图方式
考虑每一个纵轴，上端连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】文理分科

2016年12月27日2016年12月27日 Qizy 2 Comments

解题报告

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

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

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

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

选理的费用

同选理的费用

第一个很好解决，向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;
}

【TopCoder SRM590】Fox And City

2016年12月27日2016年12月30日 Qizy 22 Comments

解题报告

这题第一眼看到后觉得绝逼是一个DP
然而是网络流 QwQ

考虑原图，实际上是给定了每个点的距离上限和一些形如 ${dis_i}<={dis_j}+1$ 的关系
再考虑建边,就是更改一个点的 $dis$，注意可能会引起一系列点的 $dis$的变化
这样的话，套用BZOJ 3144的模型就可以啦！
于是跑一个最小割就好

Code

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

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

int n,E,S,T,head[N],to[M],nxt[M],flow[M],MX[N];

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 FoxAndCity {
	int dis[100][100];
    public:
    	int minimalCost(vector<string> linked, vector<int> want) {
    	    init();
    	    n = want.size();
    	    for (int i=0;i<n;i++) {
				for (int j=0;j<n;j++) {
					if (linked[i][j] == 'Y') dis[i+1][j+1] = 1;
					else dis[i+1][j+1] =  INF;
				}
			}
			Floyd();
			for (int i=2;i<=n;i++) 
				MX[i] = dis[1][i];
			init(); S = 0; T = N - 1;
			for (int i=2;i<=n;i++) {
				Add_Edge(S, id(i, 1));
				Add_Edge(id(i, MX[i]+1), T);
				for (int j=1;j<=MX[i];j++) {
					Add_Edge(id(i,j), id(i,j+1), sqr(want[i-1]-j));
					for (int k=2;k<=n;k++) {
						if (i != k && dis[i][k] == 1 && j > 1) {
							Add_Edge(id(i, j), id(k, j-1));
						}
					}
				}	
			}
			return Dinic.MaxFlow();
   		}
   	private:
   		inline void init() {
			E = 1;
			memset(head,0,sizeof(head));   
		}
		inline int id(int x, int y) {
			return (x-1) * (n+1) + y;
		}
		inline int sqr(int w) {
			return w * w;
		}
   		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 void Floyd() {
			for (int k=1;k<=n;k++) {
				for (int i=1;i<=n;i++) {
					for (int j=1;j<=n;j++) {
						dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
					}
				}
			}
		}
};

【UOJ 77】A+B Problem

2016年12月27日2016年12月28日 Qizy 78 Comments

解题报告

我们发现如果忽略$1<j<i$这个限制，再假设${l_i} = {r_i}$
这样的话，直接上最小割就好

现在考虑${l_i} < {r_i}$
这样的话，用线段树优化建图就可以啦！

再考虑$1<j<i$这个限制
这样的话，用函数式线段树就可以啦！

感觉是VFK强行套数据结构啊！
另外还有BZOJ 3218可以双倍经验！
话说BZOJ上那些$200ms+$的神犇都是用的什么算法啊？
怎么这么快啊！

Code

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

const int N = 200000+9;
const int M = 2000000;
const int INF = 1000000000;

int n,m,S,T,vout,head[N],nxt[M],to[M],flow[M];
int tot,_hash[N],A[N],W[N],B[N],LL[N],RR[N],P[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 void Add_Edge(int u, int v, int f = INF, int t = 0) {
	static int E = 1; vout += f * t;
	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 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;

namespace Persistent_Segment_Tree{
	#define PST Persistent_Segment_Tree
	int ch[N][2],root[N],cnt,pur,sur,L,R;
	
	void insert(int p, int &w, int l, int r, int f = 0) {
		if (w = ++cnt, p) {
			ch[w][0] = ch[p][0];
			ch[w][1] = ch[p][1];
			Add_Edge(p, w);
		} 
		if (f) Add_Edge(w, f);
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, w);
			else insert(ch[p][1], ch[w][1], mid, r, w);
		} else Add_Edge(sur, w);
	}
	
	inline void insert(int p, int v) {
		pur = v; sur = p;
		insert(root[p-1], root[p], 1, tot);
	}
	
	void modify(int w, int l, int r) {
		if (!w) return;
		else if (L <= l && r <= R) Add_Edge(w, pur);
		else {
			int mid = l + r + 1 >> 1;
			if (L < mid) modify(ch[w][0], l, mid-1);
			if (mid <= R) modify(ch[w][1], mid, r);
		}
	}
	
	inline void modify(int p, int node, int l, int r) {
		pur = node; L = l; R = r;
		modify(root[p], 1, tot);
	}
};

int main() {
	n = read(); PST::cnt = n << 1;
	S = 0; T = N - 1;
	for (int i=1;i<=n;i++) {
		_hash[++tot] = A[i] = read(); 
		B[i] = read();
		W[i] = read();
		_hash[++tot] = LL[i] = read();
		_hash[++tot] = RR[i] = read();
		P[i] = read();
	}
	sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) {
		A[i] = lower_bound(_hash+1, _hash+1+tot, A[i]) - _hash;
		LL[i] = lower_bound(_hash+1, _hash+1+tot, LL[i]) - _hash;
		RR[i] = lower_bound(_hash+1, _hash+1+tot, RR[i]) - _hash;
	}
	for (int i=1,l,r;i<=n;i++) {
		PST::insert(i, A[i]);
		Add_Edge(i, T, B[i], 1);
		Add_Edge(S, i, W[i], 1);
		PST::modify(i-1, i+n, LL[i], RR[i]);
		Add_Edge(i+n, i, P[i]);
	}
	printf("%d\n",vout-Dinic.MaxFlow());
	return 0;
}

【BZOJ 1497】[NOI2006] 最大获利

2016年12月27日2016年12月28日 Qizy 19 Comments

解题报告

这题先考虑一种特别简单的建图方式：

考虑使用最小割来解决这个问题
将基站放在一边，客户放在另外一边
这样的话，我们不妨规定最后在S集的表示不选择，T集选择
考虑每一条增光路，必然要割掉客户到T的路径，或者基站到S的路径

酱紫的话，岂不是刚好满足条件？

当然使用以下这种经典的建图方式可以更优地建图：

Code

第一种建图方式：

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

const int N = 55000+9;
const int M = N + 100000 << 1;
const int INF = 1e9;

int n,m,S,T,vout,head[N],nxt[M],to[M],flow[M];

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 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;
}

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() {
	n = read(); m = read();
	S = 0; T = N - 1;
	for (int i=1;i<=n;i++)
		Add_Edge(S, i, read());
	for (int i=1,t;i<=m;i++) {
		Add_Edge(read(), i+n);
		Add_Edge(read(), i+n);
		vout += (t = read());
		Add_Edge(i+n, T, t);
	}
	printf("%d\n",vout-Dinic.MaxFlow());
	return 0;
}

第二种建图方式：

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

const int N = 5000 + 9;
const int M = 100000 << 1;
const int INF = 1e9;

int n,m,S,T,vout,tmp[N],head[N],nxt[M],to[M],flow[M];

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, int t = 0) {
	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] = f * t;
}

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() {
	n = read(); m = read();
	S = 0; T = N - 1;
	for (int i=1;i<=n;i++)
		Add_Edge(i, T, read() << 1);
	for (int i=1,t,x,y;i<=m;i++) {
		x = read(); y = read();
		vout += (t = read()) * 2;
		tmp[x] += t; tmp[y] += t;
		Add_Edge(x, y, t, 1);
	}
	for (int i=1;i<=n;i++) 
		Add_Edge(S, i, tmp[i]);
	printf("%d\n",vout-Dinic.MaxFlow()>>1);
	return 0;
}

【BZOJ 3345】[Pku2914] Minimum Cut

2016年10月21日2016年10月21日 Qizy 82 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3345

这题就是一个全局最小割，其中分治最小割的做法肯定是正确的
于是水之，1.4s卡过

全局最小割专门的算法还是很优越的样子
无论是时间复杂度或是编程复杂度
但我这个蒟蒻学不会QAQ
弃坑

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
  
const int N = 850+9;
const int M = 8500*2+9;
const int INF = 100000000;
  
int head[N],nxt[M],to[M],flow[M],cur[N];
int n,m,vout=INF,cnt,id[N],dis[N],pur,T=1;
queue<int> que;
  
inline void Add_Edge(int u, int v, int w) {
    to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = w;
    to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = w;
}
  
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 bool BFS(int s, int t) {
    memset(dis,-1,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 (flow[i] && !~dis[to[i]]) 
            dis[to[i]] = dis[w] + 1, que.push(to[i]);
    }
    return ~dis[t];
}
  
int DFS(int w, int f) {
    if (w == pur) 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]));
            flow[i] -= tmp; flow[i^1] += tmp;
            ret += tmp; f -= tmp; if (!f) return ret;
        }
        return ret;
    }   
}
  
inline int Dinic(int s, int t){
    int ret = 0; pur = t;
    while (BFS(s,t)) {
        memcpy(cur,head,sizeof(head));
        ret += DFS(s,INF);
    } return ret;
}
  
void SIGN(int w) {
    dis[w] = 1;
    for (int i=head[w];i;i=nxt[i]) 
        if (!~dis[to[i]] && flow[i]) SIGN(to[i]);
}
  
void solve(int l , int r){
    if (l >= r) return ;
    static int tmp[N]; int L=l-1, R=r+1;
      
    for (int i=2;i<=T;i+=2) flow[i] = flow[i^1] = flow[i] + flow[i^1] >> 1;
    vout = min(vout, Dinic(id[l],id[r]));
      
    memset(dis,-1,sizeof(dis)); SIGN(id[l]); 
    for (int i=l;i<=r;i++) 
        if (~dis[id[i]]) tmp[++L] = id[i];
        else tmp[--R] = id[i];
    for (int i=l;i<=r;i++) id[i] = tmp[i];
    solve(l,L); solve(R,r);
}
  
int main(){
    n = read(); m = read();
    for (int i=1,u,v,w;i<=m;i++) u = read(), v = read(), w = read(), Add_Edge(u,v,w);
    for (int i=1;i<=n;i++) id[i] = i; solve(1,n); 
    printf("%d\n",vout);
    return 0;
}

【算法笔记】网络流相关·第二波冲刺

2016年9月20日2016年9月20日 Qizy 14 Comments

近日，花了4天时间再一次进行了网络流相关的专题
已经将总体进度推进到了hzwer的第四页
虽不能说硕果累累，但也是略有成效了

做题的相关感悟如下：
1）最小路径覆盖（路径问题）：出度入度拆点后跑二分图匹配
2）最大独立集：二分图建图后跑最小割
3）供求关系可以考虑二分图
4）棋盘类问题可以考虑染色
5）最大权闭合子图
6）列出数学等式，按等式的正负配合流量平衡进行建图

这一次虽然做了很多题，但注定只是一次阶段性的冲刺
因为之前有所听闻的一些经典建模方式仍然没有接触到
所以一定会有下一次冲刺哒！

【BZOJ 1391】[Ceoi2008] order

2016年9月18日2016年9月18日 Qizy 81 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1391

喜闻乐见大水题

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

const int N = 10000;
const int M = 4000000;
const int INF = 1000000000;

int n,m,head[N],nxt[M],to[M],flow[M],dis[N],cur[N],S,T,vout;
queue<int> que;

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 Add_Edge(int u, int v, int f) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}

inline bool BFS(){
    memset(dis,-1,sizeof(dis));
    dis[S] = 0; que.push(S);
    while (!que.empty()) {
        int w = que.front(); que.pop();
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
            dis[to[i]] = dis[w] + 1, que.push(to[i]);
    } return ~dis[T];
}
  
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;
    }
}
  
inline int Dinic(){
    int ret = 0; while (BFS()) {
        memcpy(cur,head,sizeof(head));
        ret += DFS(S,INF);
    } return ret;
}

int main(){
	n = read(); m = read(); S = 0; T = N-1;
	for (int i=1,t1,t2,t3;i<=n;i++) {
		t1 = read(); Add_Edge(S,i,t1); vout += t1;
		for (t2=read();t2;t2--) t3 = read(), Add_Edge(i,n+t3,read());
	}
	for (int i=1;i<=m;i++) Add_Edge(n+i,T,read());
	printf("%d\n",vout-Dinic());
	return 0;
}

【BZOJ 3275】Number

2016年9月17日2016年10月24日 Qizy 2 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3275

这题还是挺有意思的！
首先，肯定一眼能看出来是最小割
然后就是建图了。
1）暴力方法，拆点：http://hzwer.com/2864.html ←这样搞虽然不优雅，但普适性更强？←这样做是错的，详见UPD
2）优雅的方法：写个程序试一试，发现在1000以内的冲突的a,b一定是一奇一偶，于是搞成二分图

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

const int N = 3000+9;
const int M = 1000000;
const int INF = 1000000000;

int n,arr[N],head[N],nxt[M],to[M],flow[M],cur[N],dis[N],S,T,vout;
queue<int> que;

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;
}

#define sqr(x) ((x)*(x))
int GCD(int a, int b) {return b?GCD(b,a%b):a;}
inline void Add_Edge(int u, int v, int f) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}

inline bool BFS(){
    memset(dis,-1,sizeof(dis));
    dis[S] = 0; que.push(S);
    while (!que.empty()) {
        int w = que.front(); que.pop();
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
            dis[to[i]] = dis[w] + 1, que.push(to[i]);
    } return ~dis[T];
}
 
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;
    }
}
 
inline int Dinic(){
    int ret = 0; while (BFS()) {
        memcpy(cur,head,sizeof(head));
        ret += DFS(S,INF);
    } return ret;
}

int main(){
	n = read(); S = 0; T = N - 1;
	for (int i=1;i<=n;i++) arr[i] = read(), vout += arr[i];
	for (int i=1;i<=n;i++) if (arr[i]%2) Add_Edge(S,i,arr[i]); else Add_Edge(i,T,arr[i]);
	for (int i=1;i<=n;i++) if (arr[i]%2) for (int j=1,w=sqr(arr[i])+sqr(arr[j]);j<=n;j++,w=sqr(arr[i])+sqr(arr[j])) 
		if (GCD(arr[i],arr[j])==1 && sqr(int(sqrt(w)+1e-7))== w) Add_Edge(i,j,INF);
	printf("%d\n",vout-Dinic());
	return 0;
}

—– UPD 2016.9.17 —–
给一下证明：
首先同为偶数肯定不成立。
对于同为奇数的情况：
(2a-1)^2+(2b-1)^2=c^2
c^2=4(a(a-1)+b(b-1))+2
不难发现c^2中只有一个2，没有两个2
所以c不可能为整数
得证.

—– UPD 2016.9.18 —–
今天突然想到，如果hzwer那种建模可以在一般图中推广的话
那我们还要带花树干嘛？
所以这题黄学长没证二分图就艹过去了，这完全是运气好啊！
但再仔细想一想，如果是带花树的题，岂不是可以尝试这样去骗分？

【BZOJ 2127】happiness

2016年9月17日2016年9月17日 Qizy 26 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2127
数据传送门：http://pan.baidu.com/s/1c1Ldkp6

这题的输入数据我已无力吐槽……
为此wa了两个小时

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

const int L = 100+9;
const int N = 10000+9;
const int M = 500000+9;
const int INF = 100000000;

int head[N],nxt[M],to[M],flow[M],n,m,vout,wen[L][L],li[L][L];
int dis[N],cur[N],S,T; queue<int> que; 

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;
}

#define id(i,j) ((i)+((j)-1)*n)
inline void Add_Edge(int u, int v, int f) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = f;
}

inline bool BFS(){
    memset(dis,-1,sizeof(dis));
    dis[S] = 0; que.push(S);
    while (!que.empty()) {
        int w = que.front(); que.pop();
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
            dis[to[i]] = dis[w] + 1, que.push(to[i]);
    } return ~dis[T];
}
  
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;
    }
}
  
inline int Dinic(){
    int ret = 0; while (BFS()) {
        memcpy(cur,head,sizeof(head));
        ret += DFS(S,INF);
    } return ret;
}

int main(){
	m = read(); n = read(); S = 0; T = N-1;
	for (int i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) vout += (tmp = read()), wen[i][j] += tmp*2;
	for (int i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) vout += (tmp = read()), li[i][j] += tmp*2;
	for (int i=1;i<n;i++) for (int j=1,tmp;j<=m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i+1,j),tmp), wen[i][j] += tmp, wen[i+1][j] += tmp;
	for (int i=1;i<n;i++) for (int j=1,tmp;j<=m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i+1,j),tmp), li[i][j] += tmp, li[i+1][j] += tmp;
	for (int i=1;i<=n;i++) for (int j=1,tmp;j<m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i,j+1),tmp), wen[i][j] += tmp, wen[i][j+1] += tmp;
	for (int i=1;i<=n;i++) for (int j=1,tmp;j<m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i,j+1),tmp), li[i][j] += tmp, li[i][j+1] += tmp;
	for (int i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) Add_Edge(S,id(i,j),wen[i][j]), Add_Edge(id(i,j),T,li[i][j]);
	printf("%d\n",vout-Dinic()/2);
	return 0;
}

【BZOJ 2132】圈地计划

2016年9月17日2016年9月17日 Qizy 25 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2132

可以说是最经典的一种最小割建模了吧！
看一看这张图片就能知道他的重要性了：

然而做题的时候，只能确定是染色后转二分图，并没有确定该如何建图QAQ
题解的话，让我们召唤Menci:https://oi.men.ci/bzoj-2132/

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

const int L = 100+9;
const int N = L*L+9;
const int M = N*15;
const int INF = 1000000000;

int head[N],nxt[M],to[M],flow[M],n,m,A[L][L],B[L][L],C[L][L],vout;
int S,T,dis[N],cur[N]; queue<int> que;

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;
}

#define id(i,j) (i+((j)-1)*n)
inline void Add_Edge(int u, int v, int f) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = f;
}

inline bool BFS(){
    memset(dis,-1,sizeof(dis));
    dis[S] = 0; que.push(S);
    while (!que.empty()) {
        int w = que.front(); que.pop();
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
            dis[to[i]] = dis[w] + 1, que.push(to[i]);
    } return ~dis[T];
}
 
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;
    }
}
 
inline int Dinic(){
    int ret = 0; while (BFS()) {
        memcpy(cur,head,sizeof(head));
        ret += DFS(S,INF);
    } return ret;
}

int main(){
	m = read(); n = read(); S = 0; T = N-1;
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) vout += (A[i][j] = read());
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) vout += (B[i][j] = read());
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) C[i][j] = read();
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
		if (i+j & 1) Add_Edge(S,id(i,j),A[i][j]), Add_Edge(id(i,j),T,B[i][j]);
		else Add_Edge(S,id(i,j),B[i][j]), Add_Edge(id(i,j),T,A[i][j]);
		if (j > 1 && i+j&1) Add_Edge(id(i,j),id(i,j-1),C[i][j]+C[i][j-1]), vout += C[i][j]+C[i][j-1];
		if (i > 1 && i+j&1) Add_Edge(id(i,j),id(i-1,j),C[i][j]+C[i-1][j]), vout += C[i][j]+C[i-1][j];
		if (j < m && i+j&1) Add_Edge(id(i,j),id(i,j+1),C[i][j]+C[i][j+1]), vout += C[i][j]+C[i][j+1];
		if (i < n && i+j&1) Add_Edge(id(i,j),id(i+1,j),C[i][j]+C[i+1][j]), vout += C[i][j]+C[i+1][j];
	} printf("%d\n",vout-Dinic());
	return 0;
}

【BZOJ 2768】[JLOI2010] 冠军调查

2016年9月17日2016年9月17日 Qizy 3 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2768

真·双倍经验
同BZOJ_1934

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

const int N = 300+9;
const int M = N*N*2;
const int INF = 10000000;

int head[N],nxt[M],to[M],flow[M],n,m,dis[N],S,T,cur[N];
queue<int> que;

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 Add_Edge(int u, int v, int f) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = f;
}

inline bool BFS(){
    memset(dis,-1,sizeof(dis));
    dis[S] = 0; que.push(S);
    while (!que.empty()) {
        int w = que.front(); que.pop();
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
            dis[to[i]] = dis[w] + 1, que.push(to[i]);
    } return ~dis[T];
}
 
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;
    }
}
 
inline int Dinic(){
    int ret = 0; while (BFS()) {
        memcpy(cur,head,sizeof(head));
        ret += DFS(S,INF);
    } return ret;
}

int main(){
	n = read(); m = read(); S = 0; T = n+1;
	for (int i=1;i<=n;i++) if (!read()) Add_Edge(S,i,1); else Add_Edge(i,T,1);
	for (int i=1,a,b;i<=m;i++) a = read(), b = read(), Add_Edge(b,a,1);
	printf("%d\n",Dinic()); 
	return 0;
}

相关链接

解题报告

相关链接

解题报告

题目大意

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code