朝花夕拾-分治最小割

Posted on Edited on

对于询问网络图中每个点对的最大流（最小割容量），总是可以将图简化成n个点n-1条边的树型图，边上标有一些容量，使得在树上询问每个点对的最大流等价于原问题。

上文提到的树叫作Gomory–Hu tree，其构造方法是：

  1. 将所有点的放在一个集合中。
  2. 选一个元素个数至少为2的集合（不妨设其为集合R）中任取两个点作为原图的源点和汇点，跑一次最大流，就会将原图上的所有点分割为两部分，要么与S联通，要么与T联通。
  3. 在残余图中，对于每个节点v∈R，若v与S联通，则v留在集合R，否则将v移除并放置于新集合R'中。在Gomory–Hu tree中，有边(R,R')，边权（容量）是2.中最大流的值。
  4. 还原原网络图，重复2，3，4至所有集合有且仅有一个元素。此时Gomory–Hu tree建图完毕。

询问网络图中每个点对的最大流，等价于询问Gomory–Hu tree上对应点路径边权的最小值，可以用树链剖分维护。

bzoj4519 不同的最小割

cuts

问题描述

学过图论的同学都知道最小割的概念：对于一个图，某个对图中结点的划分将图中所有结点分成
两个部分，如果结点 s,t 不在同一个部分中，则称这个划分是关于 s,t 的割。对于带权图来说，将
所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 s,t 的最小割指的是在
关于 s,t 的割中容量最小的割。
而对冲刺 NOI 竞赛的选手而言，求带权图中两点的最小割已经不是什么难事了。我们可以把
视野放宽，考虑有 N 个点的无向连通图中所有点对的最小割的容量，共能得到 N ( N ? 1)
2 个数值。
这些数值中互不相同的有多少个呢？这似乎是个有趣的问题。

输入格式

输入文件第一行包含两个数 N， M，表示点数和边数。接下来 M 行，每行三个数 u， v， w，表示
点 u 和点 v（从 1 开始标号）之间有条边权值是 w。

输出格式

输出文件第一行为一个整数，表示个数。

样例输入

4 4
1 2 3
1 3 6
2 4 5
3 4 4

样例输出

3

范围约定

? 对于 50% 的数据， N ≤ 200， M ≤ 2000
? 对于 100% 的数据， 1 ≤ N ≤ 850， 1 ≤ M ≤ 8500， 1 ≤ w ≤ 100000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cassert>
using namespace std;

void ri(int&);

const int MAXN = 860, M = 8510*4, INF = 1<<29;

int n, m;

int to[M], nex[M], index[MAXN], mcap[M], cap[M], cur=0;
int pn[MAXN], tmppn[MAXN];

void addEdge(int a, int b, int cap);

int q[MAXN], qh, qt, flag[MAXN], fa[MAXN], path[MAXN], FLOW[MAXN], cntf=0;

int bfs(int S, int T)
{
	qh = 0; qt = 1;
	memset(flag, -1, sizeof(int)*(n+3));
	flag[S] = 1;
	q[0] = S;
	while (qh < qt)
	{
		int x = q[qh++];
		for (int i=index[x]; i!=-1; i=nex[i])
		{
			if (flag[to[i]]==-1 && cap[i]>0)
			{
				flag[to[i]] = flag[x]+1;
				q[qt++] = to[i];
			}
		}
	}
	return flag[T];
}

void Dinic(int S, int T)
{
	int depth;
	int flow = 0;
	while(bfs(S, T)!=-1)
	{
		fa[depth=1] = S;
		while (0 < depth)
		{
			if (fa[depth] == T)
			{
				int minc = INF, mink;
				for (int i=1; i<depth; ++i)
				{
					if (cap[path[i]] < minc)
					{
						minc = cap[path[i]];
						mink = i;
					}
				}
				flow += minc;
				for (int i=1; i<depth; ++i)
				{
					cap[path[i]] -= minc;
					cap[path[i]^1]+= minc;
				}
				
				depth = mink;
			}
			bool alive = false;
			for (int i=index[fa[depth]]; i!=-1; i=nex[i])
			{
				if (flag[fa[depth]]+1==flag[to[i]] && cap[i]>0)
				{
					path[depth] = i;
					fa[++depth] = to[i];
					alive = true;
					break;
				}
			}
			if (!alive) { flag[fa[depth]] = -1; --depth; }
		}
	}
	FLOW[cntf++] = flow;
}

void dfs(int l, int r)
{
	if (l==r) return;
	memcpy(cap, mcap, sizeof(int)*cur);
	Dinic(pn[l], pn[r]);
	int lpart = l-1, rpart = r+1;
	for (int i=l; i<=r; ++i)
	{
		if (flag[pn[i]]!=-1)
			tmppn[++lpart] = pn[i];
		else
			tmppn[--rpart] = pn[i];
	}
	for (int i=l; i<=r; ++i)
	{
		pn[i] = tmppn[i];
	}
	dfs(l, lpart);
	dfs(rpart, r);
}

int main()
{
	freopen("cuts.in", "r", stdin);
	freopen("cuts.out", "w", stdout);
	memset(index, -1, sizeof(index));
	ri(n);
	ri(m);
	for (int i=0, a, b, c; i<m; ++i)
	{
		ri(a); ri(b); ri(c);
		addEdge(a, b, c);
		addEdge(b, a, c);
//		assert(cur < 8500*4);
	}
	for (int i=1; i<=n; ++i) pn[i] = i;

	dfs(1, n);

	sort(FLOW, FLOW+cntf);
	
	int ans = 1;
	
	for (int i=1; i<cntf; ++i)
	{
		if (FLOW[i]!=FLOW[i-1]) ++ans;
	}

	printf("%d\n", ans);

	return 0;
}

inline void addEdge(int a, int b, int c)
{
	to[cur] = b; mcap[cur] = c; nex[cur] = index[a]; index[a] = cur++;
	to[cur] = a; mcap[cur] = 0; nex[cur] = index[b]; index[b] = cur++;
}

inline void ri(int &x)
{
	char c;
	while ((c=getchar())<'0' || '9'<c);
	x = c-'0';
	while ('0'<=(c=getchar()) && c<='9')
		x = 10*x + c-'0';
//	cerr << x << endl;
}