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

【日常小测】Mortal Kombat

题目大意

给定$n(n \le 300)$个外星人,给定$m(m \le 1500)$个地球人,再给定任意地球人与外星人的关系
关系由一个$nm$的0/1矩阵给出,表示第$i$个外星人是否能与第$j$个地球人配对
要求每个外星人至少与一个地球人配对,地球人只能与至多一个外星人匹配
问由哪些关系一定不可能出现在合法的匹配方案中

解题报告

这是一道基础图论题

我们可以先来考虑一个简单的版本:地球人个数与外星人一样
那么我们可以先用二分图匹配跑一个完备匹配出来
此时在匹配中的边一定可以出现在合法的匹配方案中

只考虑不在当前匹配中的边,那么一定是走一条像增广路一样的东西
就是一条匹配边,一条非匹配边交叉着走。最后走一个偶环绕回来
于是我们对于从左边连到右边的边,只保留非匹配边
对于从右到左的边,我们只保留匹配边。这样就可以保证是偶环了
至于能不能走回来,我们发现这就是一个有向图的强连通分量
于是我们再跑一个Tarjan,判断一下就可以了

现在考虑地球人与外星人不等的情况
我们可以把外星人补到与地球人一样多啊!
就是加一些可以与所有地球人匹配的外星人就可以了
当然不加点,大力讨论一波也是可以的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 3009;
const int M = N * N << 1;
const int INF = 1e9;
  
int head[N],nxt[M],to[M],flow[M],low[N],dfs[N];
int n,m,S,T,E=1,mth[N],id[N][N],num[N],ins[N]; char pat[N]; 
stack<int> stk;
  
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 f=0) {
    if (f) {
        to[++E] = v; nxt[E] = head[u]; head[u] = E;
        to[++E] = u, nxt[E] = head[v], head[v] = E;
        flow[E - 1] = f; return E - 1;
    } else to[++E] = v, nxt[E] = head[u], head[u] = E;
}
  
class Network_Flow{
    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:
        int DFS(int w, int f) {
            if (w == T) return f; int ret = 0;
            for (int &i=cur[w],tmp;i;i=nxt[i]) {
                if (flow[i] && dis[to[i]] == dis[w] + 1) {
                    tmp = DFS(to[i], min(f, flow[i]));
                    flow[i] -= tmp; flow[i^1] += tmp;
                    f -= tmp; ret += tmp;
                    if (!f) return ret;
                }
            } return ret;
        }
        inline bool BFS() {
            memset(dis,60,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]] > INF) {
                        dis[to[i]] = dis[w] + 1; 
                        que.push(to[i]);
                    }
                }
            } return dis[T] < INF;
        }
}Dinic;
 
void Tarjan(int w) { 
    static int dfs_cnt = 0, scc_cnt = 0; 
    dfs[w] = low[w] = ++dfs_cnt; stk.push(w); ins[w] = 1;
    for (int i=head[w];i;i=nxt[i]) {
        if (!dfs[to[i]]) Tarjan(to[i]), low[w] = min(low[w], low[to[i]]);
        else if (ins[to[i]]) low[w] = min(low[w], dfs[to[i]]);  
    }
    if (low[w] == dfs[w]) {
        for (scc_cnt++;!stk.empty();stk.pop()) {
            num[stk.top()] = scc_cnt; ins[stk.top()] = 0;
            if (stk.top() == w) {stk.pop(); break;}
        }
    }
}
 
int main() {
    n = read(); m = read(); S = 0; T = N - 1;
    memset(id, -1, sizeof(id));
    for (int i=1;i<=n;i++) {
        scanf("%s",pat+1);
        for (int j=1;j<=m;j++) {
            if (pat[j] == '1') {
                id[i][j] = AddEdge(i, m + j, 1);
            }   
        }
    } 
    for (int i=1;i<=n;i++) AddEdge(S, i, 1);
    for (int i=1;i<=m;i++) AddEdge(m + i, T, 1);
    if (Dinic.MaxFlow() != n) {
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) putchar('1');
            puts("");
        }
    } else {
        E = 1; memset(head,0,sizeof(head));
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) 
            if (~id[i][j] && !flow[id[i][j]]) {mth[j] = i; break;}
        for (int i=n+1,j=1;i<=m;i++,j++) {while(mth[j])j++;mth[j]=i;}
        for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) if (~id[i][j] || i > n) {
            if (mth[j] == i) AddEdge(m+j, i); else AddEdge(i, m+j);}
        for (int i=1;i<=m*2;i++) if (!dfs[i]) Tarjan(i);
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                if ((~id[i][j]) && (mth[j] == i || num[i] == num[m+j])) putchar('0');
                else putchar('1');
            } putchar('\n');
        }
    }
    return 0;
}

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

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

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

【TopCoder SRM578】DeerInZooDivOne

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/12/DeerInZooDivOne.html
中文题面:http://paste.ubuntu.com/23693088/
官方题解:https://apps.topcoder.com/wiki/display/tc/SRM+578

解题报告

给定一棵树,让你求两个没有重叠部分的连通块,使得这个连通块同构

这样的话,真的是不会啊!
直接说正解吧!

枚举将两个连通块分开的那条边
定义 \(f(i,j)\) 为以i的子树和j的子树最大同构部分有多大
不难发现答案就是 \(\max (f(i,j))\)

考虑如何求 \(f(i,j)\):
递归处理的话,实际上就是将两个节点的儿子进行配对
于是搞在这里搞二分图带权匹配就可以啦!

Code

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

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

int n,m,S,T;

class Minimum_Cost_Flow{
	int head[N],nxt[M],to[M],flow[M],cost[M];
    int E,vout,dis[N],sur[N],inq[N];
    queue<int> que;
    public:
    	inline void init() {
			E = 1; S = 0; T = N - 1;
			memset(head,0,sizeof(head));
		}
        inline void Add_Edge(int u, int v, int f, int c) {
			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;
		}
        inline int MaxFlow() {
        	vout = 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;
                vout += dis[T] * f;
            }
            return vout;
        }
    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 DeerInZooDivOne {
	int ret,t1,t2,q1[N],q2[N],fa[N],f[N][N];
	int E,head[N],to[M],nxt[M],vis[N];
    public:
    	int getmax(vector<int> a, vector<int> b) {
    	    n = a.size(); init();
    	    for (int i=0;i<n;i++) 
				Add_Edge(a[i]+1, b[i]+1);
			for (int i=0;t1=t2=0,i<n;i++) {
				DFS(a[i]+1, b[i]+1, q1, t1);
				DFS(b[i]+1, a[i]+1, q2, t2);
				vis[i*2+1] = vis[(i+1)*2] = 1;
				for (int p1=1;p1<=t1;p1++) {
					Make_Root(q1[p1], q1[p1]);
					for (int p2=1;p2<=t2;p2++) {
						Make_Root(q2[p2], q2[p2]);
						memset(f,-1,sizeof(f));
						ret = max(ret, F(q1[p1], q2[p2]));
					}
				}
				vis[i*2+1] = vis[(i+1)*2] = 0;
			}
			return ret;
		}
   	private:
   		inline void init() {
			E = 0; ret = 1;
			memset(head,0,sizeof(head));		
		}
   		inline void Add_Edge(int u, int v) {
			to[++E] = v; nxt[E] = head[u]; head[u] = E; 
			to[++E] = u; nxt[E] = head[v]; head[v] = E;   
		}
		void DFS(int w, int f, int *arr, int &cnt) {
			arr[++cnt] = w; 
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f) {
					DFS(to[i], w, arr, cnt);
				}
			}
		}
		void Make_Root(int w, int f) {
			fa[w] = f;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[i]) {
					Make_Root(to[i], w);
				} 
			}
		}
		inline int F(int a, int b) {
			if (a > b) swap(a, b);
			if (~f[a][b]) return f[a][b];
			else {
				for (int i=head[a];i;i=nxt[i]) {
					if (to[i] != fa[a] && !vis[i]) {
						for (int j=head[b];j;j=nxt[j]) {
							if (to[j] != fa[b] && !vis[j]) {
								F(to[i], to[j]);	
							}
						}
					}
				}
				MCMF.init();
				for (int i=head[a];i;i=nxt[i]) {
					if (to[i] != fa[a] && !vis[i]) {
						MCMF.Add_Edge(S, to[i], 1, 0);
						for (int j=head[b];j;j=nxt[j]) {
							if (to[j] != fa[b] && !vis[j]) {
								MCMF.Add_Edge(to[i], to[j], 1, -F(to[i], to[j]));	
							}
						}
					}
				}
				for (int i=head[b];i;i=nxt[i]) {
					if (to[i] != fa[b] && !vis[i]) {
						MCMF.Add_Edge(to[i], T, 1, 0);
					}
				}
				f[a][b] = -MCMF.MaxFlow();
				return ++f[a][b];
			}
		}
};

【TopCoder SRM590】Fox And City

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/12/FoxAndCity.html
中文题面:http://paste.ubuntu.com/23693047/

解题报告

这题第一眼看到后觉得绝逼是一个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]);
					}
				}
			}
		}
};

【BZOJ 3876】[AHOI2014] 支线剧情

相关链接

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

解题报告

就是裸的上下界费用流
但是合并一下边,快了30倍是什么鬼啊

Code

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

const int N = 300 + 9;
const int M = 20000 + 100 << 1;
const int INF = 1e9;

int n,m,vout,T,S,V,cnt[N],head[N],to[M],nxt[M],cost[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, 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; 
}

class Minimum_Cost_Flow{
	int dis[N],sur[N],inq[N];
	queue<int> que;
    public:
    	inline void MaxFlow(bool SPJ=0) {
			for (int f=INF,w;SPFA();f=INF) {
				if (SPJ && dis[T] >= 0) return;
				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;
				vout += dis[T] * f;
			}
		}
	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;

int main() {
	n = read();
	S = 0; T = N - 1; V = N - 2;
	for  (int i=1,k;i<=n;i++) {
		k = read();
		for (int j=1,p,c;j<=k;j++) {
			p = read(); c = read();
			cnt[i]--; cnt[p]++;
			vout += c;
			Add_Edge(i, p, INF, c);
		}
		Add_Edge(i, V, INF, 0);
	}
	Add_Edge(V, 1, INF, 0);
	for (int i=1;i<=n;i++) {
		if (cnt[i] > 0) Add_Edge(S, i, cnt[i], 0);
		else Add_Edge(i, T, -cnt[i], 0);
	}
	MCMF.MaxFlow();
	for (int i=head[S];i;i=nxt[i]) 
		if (flow[i]) return 1;
	S = V; T = 1;
	MCMF.MaxFlow(1);
	printf("%d\n",vout);
	return 0;
}

【UOJ 77】A+B Problem

相关链接

题目传送门:http://uoj.ac/problem/77
神犇题解:http://www.cnblogs.com/geng4512/p/5296863.html

解题报告

我们发现如果忽略\(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] 最大获利

相关链接

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

解题报告

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

考虑使用最小割来解决这个问题
将基站放在一边,客户放在另外一边
这样的话,我们不妨规定最后在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;
}

【算法笔记】上下界网络流问题

无源汇可行流

  1. 问题分析:
    因为只比传统网络流多了下界,所以考虑单独考虑下界的流量

  2. 解决方案:
    于是原来的边拆为上界为min的边并强行满流,和上界为max - min的边。
    但这样可能会出现流量不平衡的状况,及一个点流入的流量不等于流出量。
    于是单独增加源汇点,构造一个完全等价的网络流问题

    至此我们已经将问题转化为传统网络流问题,直接求解即可。
    如何判断是否有可行流的根据也显而易见了:\( Max\_Flow = = \sum {Min\_Flo{w_i}}\)

有源汇可行流

  1. 问题分析:
    有源汇意味着有一对点的流量不守恒,就是这一对点使其于无源汇可行流问题有了差别
    于是我们考虑去掉这个不同点,将其转化为无源汇可行流

  2. 解决方案
    我们注意到,将源汇点连上一条容量INF的边之后,所有的点流量都守恒了
    换一句话来说我们将其转化为了无源汇可行流问题,使用上文所述方法求解即可

有源汇最大流/最小流

  1. 通解通法:
    观察可行流的解决方案,不难发现我们控制我们人为增加的那条边的容量即可控制最大流的容量
    所以我们可以二分最大流/最小流,之后进行可行流判断,再之后根据结果进行调整即可

  2. 最小流的高效算法:
    先不连t-s的那条容量为INF的边,先跑一次附加源汇的最大流
    连t-s的那条边,在残量网络上继续跑附加源汇最大流
    此时t-s那条边的流量是最小的,使用上文所述方法判断其是否为可行流即可

  3. 最大流的高效算法
    连t-s的那条容量为INF的边,跑一次附加源汇最大流
    连t-s的那条边,在残量网络上继续跑s-t的最大流
    此时t-s那条边的流量是最小的,使用上文所述方法判断其是否为可行流即可

【BZOJ 2095】[Poi2010] Bridges

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

这个题目啊!瞄一眼就知道是二分吧?
接下来就是给你一些有向边&无向边,让你判断是否存在欧拉回路

对于有向边,没有悬念,直接记录对于出度入度的贡献
只与有向边嘛,不妨先随便定一个向,然后考虑使用网络流进行调整
具体细节可以参见:http://blog.csdn.net/wzq_qwq/article/details/48651379

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 2000+9;
const int M = 10000+9;
const int INF = 1e9;

struct Edge{int u,v,w1,w2;}edge[M];
int n,m,MX,MN=INF,in[N],out[N],cur[M];
int S,T,dis[N],flow[M],head[N],nxt[M],to[M],TT; 
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) {
	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(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 == T) {
		return f;
	} else {
		int ret = 0;
		for (int &i=cur[w],tmp;i && f;i=nxt[i]) { 
			if (dis[to[i]] == dis[w] + 1) {
				tmp = DFS(to[i], min(f, flow[i]));
				ret += tmp; f -= tmp;
				flow[i] -= tmp; flow[i^1] += tmp;
			}
		}
		return ret;
	}
}

inline int Dinic(){
	int ret = 0;
	while (BFS()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	}
	return ret;
}

inline bool judge(int lim){
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	memset(head,0,sizeof(head));
	S = 0; T = N - 1; TT = 1;
	int tot = 0;
	
	for (int i=1;i<=m;i++) {
		if (lim < edge[i].w1) {
			continue;
		} else if (lim < edge[i].w2) {
			in[edge[i].v]++;
			out[edge[i].u]++;
		} else {
			in[edge[i].v]++;
			out[edge[i].u]++;
			Add_Edge(edge[i].u, edge[i].v, 2);
		}
	}
	
	for (int i=1;i<=n;i++) {
		if (abs(in[i]-out[i]) & 1) {
			return false;
		} else if (in[i] < out[i]) {
			Add_Edge(S,i,out[i]-in[i]);	
			tot += out[i] - in[i];
		} else if (in[i] > out[i]) {
			Add_Edge(i,T,in[i]-out[i]);
		}
	}
	
	return Dinic() == tot;
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		edge[i].u = read();
		edge[i].v = read();
		edge[i].w1 = read();	
		edge[i].w2 = read();
		if (edge[i].w1 > edge[i].w2) {
			swap(edge[i].w1, edge[i].w2);
			swap(edge[i].u, edge[i].v);
		}
		MX = max(MX, edge[i].w2);
		MN = min(MN, edge[i].w1);
	}
	
	int l = MN, r = MX, mid, ret = -1;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid)) ret = mid, r = mid - 1;
		else l = mid + 1;
	}
	if (~ret) printf("%d\n",ret);
	else puts("NIE");
	return 0;
}

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

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

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

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

【COGS 746】[网络流24题] 骑士共存

题目传送门:http://cojs.tk/cogs/problem/problem.php?pid=746

好吧,我承认我看的是题解……
推荐这家的题解:https://oi.men.ci/cogs-746/

自己来说的话,就是搞一搞二分图?
染色之后,发现有冲突的点都在不同的集合内
于是连边,跑最小割即可

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

const int N = 40000+9;
const int M = N*10;
const int L = 200+9;
const int INF = 10000000;

int head[N],nxt[M],to[M],flow[M],cur[N],dis[N];
int n,m,mat[L][L],vout,S,T; 
int dx[]={0,2,1,-1,-2,-2,-1,1,2};
int dy[]={0,1,2,2,1,-1,-2,-2,-1};
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(x,y) ((x)+((y)-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] = 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(){
	freopen("knight.in","r",stdin);
	freopen("knight.out","w",stdout);
	n = read(); m = read(); S = 0; T = N-1; vout = n*n;
	for (int i=1,x,y;i<=m;i++) x = read(), y = read(), mat[x][y] = 1, vout--;
	for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) if (!mat[i][j]) 
		if ((i+j)&1) {
			Add_Edge(S,id(i,j),1); 
			for (int k=1,x,y;k<=8;k++) {
				x = i + dx[k]; y = j + dy[k];
				if (1 <= x && x <= n && 1 <= y && y <= n && !mat[x][y])
					Add_Edge(id(i,j),id(x,y),INF);
			}
		} else Add_Edge(id(i,j),T,1);
	vout -= Dinic();
	printf("%d\n",vout);
	return 0;
}