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

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

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

【BZOJ 3345】[Pku2914] Minimum Cut

题目传送门: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;
}