mydcwfy's Blog

P3329

Posted on
Symbols count in article: 3.1k Reading time ≈ 7 mins.

最小割树的模板题。

1. 前置知识

最小割树（Gomory-Hu Tree）

如果你不知道，可以看 网络流 或 最小割树 （ 都是我的博客 ）

当然，你也可以看一下下面的解释。

2. 最小割树（Gomory-Hu Tree）

（ 这也是来自我的博客 ）

很明显，不可能每次求最小割（复杂度为 $O(n^4m)$）。

我们将一个网络流的图转化为一棵树，其中原图 $u$ 到 $v$ 的最小割即为转化到树上。

树的一个性质是：删除一条边，树变得不连通。

那么，我们可以任意选 2 个点 $s$ 与 $t$，跑最小割（即最大流），然后再连一条从 $s$ 到 $t$ 的边。

又 Dinic 算法最后一次 bfs 相当于求一个最小割，原图就被分为了两部分。

最后分治就可以了，复杂度为 $O(n^3m)$（Dinic 跑不满的，所以不会超时）。

按这样建出的树，就是一棵无根树。

我们可以发现一个有趣的性质：$u$ 到 $v$ 的最小割就是树上从 $u$ 到 $v$ 的所有路径长的最小值。

可以感性地理解一下（ 主要是太菜不会证 ）：最小割即为最小的路径长，把 $u$ 到 $v$ 的任意一条路径切断，都是割。

3. 回归本题

还是比较简单。

直接预处理，将所有的点对之间的最小割求出来。

有一下两种做法。

1） 直接扫描

由于出题人比较良心，这个题的 $Q$ 比较少，可以通过 $O(Qn^2)$，还是可以过的。

2） 使用有序排列

我们也可以先将所有的最小割排序好，每次询问，直接查询在有序数列中的位置，减下标即可。

我太懒了，使用了第一种。

4. Code

注意要建双向边，否则就不是两边都可以被割掉了。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const int N=1005,M=1e5+10;
const ll INF=1e15;

int h[N],e[M],ne[M],idx;
ll w[M],ans[N][N];
int cur[N],d[N],q[N],S,T,n,m;
int node[N],tmp1[N],tmp2[N];

void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
	e[idx]=a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}

bool bfs()
{
	memset(d,0,sizeof d);
	int hh=1,tt=1;
	q[1]=S;cur[S]=h[S];d[S]=1;
	while (hh<=tt)
	{
		int x=q[hh++];
		for (int i=h[x];~i;i=ne[i])
			if (!d[e[i]]&&w[i])
			{
				d[e[i]]=d[x]+1;
				cur[e[i]]=h[e[i]];
				if (e[i]==T) return true;
				q[++tt]=e[i];
			}
	}
	return false;
}

int findflow(int x,ll limit)
{
	if (x==T) return limit;
	ll flow=0;
	for (int i=cur[x];~i&&flow<limit;i=ne[i])
	{
		cur[x]=i;
		if (d[e[i]]==d[x]+1&&w[i])
		{
			int t=findflow(e[i],min(w[i],limit-flow));
			if (!t) d[e[i]]=-1;
			w[i]-=t,w[i^1]+=t,flow+=t;
		}
	}
	return flow;
}

void init()
{
	for (int i=0;i<idx;i+=2)
		w[i]=(w[i]+w[i^1]),w[i^1]=0;
	return;
}

ll dinic()
{
	init();
	ll r=0,flow;
	while (bfs()) while (flow=findflow(S,INF)) r+=flow;
	return r;
}

void work(int l,int r)
{
	if (l==r) return ;
	S=node[l],T=node[l+1];
	ll t=dinic();
    int s=node[l],tt=node[l+1];
	ans[T][S]=ans[S][T]=t;
//	printf("%d %d:%d\n",S,T,ans[S][T]);
	int cnt1=0,cnt2=0;
	for (int i=l;i<=r;++i)
		if (d[node[i]]) tmp1[++cnt1]=node[i];
		else tmp2[++cnt2]=node[i];
	for (int i=1;i<=cnt1;++i) node[i+l-1]=tmp1[i];
	for (int i=1;i<=cnt2;++i) node[cnt1+l+i-1]=tmp2[i];
	work(l,l+cnt1-1);
	work(l+cnt1,r);
	for (int i=1;i<=cnt1;++i)
		for (int j=1;j<=cnt2;++j)
		{
			int ii=node[i+l-1],jj=node[j+cnt1+l-1];
			ans[jj][ii]=ans[ii][jj]=min(min(ans[ii][s],ans[s][tt]),ans[tt][jj]);
		}
	return;
}

int main()
{
    int Case=0;cin>>Case;
    while (Case--)
    {
        memset(h,-1,sizeof h);
        idx=0;
        cin>>n>>m;
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j) ans[i][j]=INF;
        int x,y;
        ll z;
        while (m--)
        {
            scanf("%d %d %lld",&x,&y,&z);
            add(x,y,z);add(y,x,z);
        }
        for (int i=0;i<=n;++i) node[i]=i;
        work(1,n);
        int que;cin>>que;
        while (que--)
        {
            scanf("%lld",&z);
            int tot=0;
            for (int i=1;i<=n;++i)
                for (int j=1;j<=n;++j)
                    if (ans[i][j]<=z) tot++;
            printf("%d\n",tot/2);
        }
        puts("");
    }
	return 0;
}