小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话： ”对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。
对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割“
现给定一张无向图，小白有若干个形如”图中有多少对点它们的最小割的容量不超过x呢“的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为仍然是小蓝的好友，你又有任务了。
输入文件第一行有且只有一个正整数T，表示测试数据的组数。 对于每组测试数据， 第一行包含两个整数n,m，表示图的点数和边数。 下面m行，每行3个正整数u,v,c(1<=u,v<=n,0<=c<=106)，表示有一条权为c的无向边(u,v) 接下来一行，包含一个整数q，表示询问的个数 下面q行，每行一个整数x，其含义同题目描述。
输出格式：对于每组测试数据，输出应包括q行，第i行表示第i个问题的答案。对于点对(p,q)和(q,p)，只统计一次（见样例）。两组测试数据之间用空行隔开。
1 5 0 1 0
10
【数据范围】
对于100%的数据 T<=10,n<=150,m<=3000,q<=30，x在32位有符号整数类型范围内。
图中两个点之间可能有多条边
此题最开始想，肯定是想O(n2)枚举，再加上网络流玄学的复杂度，显然是过不了的，所以这题就要用到最小割树，Gomory_tree的思想，
以下结论参考国家集训队论文2016<<浅谈无向图最小割问题的一些算法及应用>>王文涛
1.对于任意不同的三点a,b,c，a,b的最小割一定大于a,c或b,c的最小割由此推广得λ(u, v) ≥ min (λ(u, w1), λ(w1, w2), . . . , λ(wk, v))（λ（a,b）是指a,b的最小割）所以可以证明，对于任意的u,v，取s,t为u,v在最小割树上唯一路径λ（s，t）最小的点对，则λ（u，v）>=λ（s，t），又根据定义得u，v在λ（s，t）割集的两侧，因此λ（u，v）<=λ（s，t），所以λ（u，v）==λ（s，t），即u，v树上唯一路径上的最小边权即为λ（u，v），于是我们可以证明u，v的最小割就是在Gomory_tree上u，v的路径上的最小边权，用简洁的更容易理解的话来说，就是若存在（s，t）的最小割能够将u，v分成两部分，且λ（s，t）是在所有能将（u，v）分成两部分的最小割中最小的，则λ（u，v）等于λ（s，t）
2.可以证明，λ（u，v）是子模函数，对称函数以及反模函数，可以根据论文上的过程来证明，因此，对于两点（s，t）的一个最小割分成的两组点集，表示为α（s，t），设W为一侧的点集，设u，v均为W中的点，则根据以上三种函数的性质可以证明u，v的最小割一定位于W这一侧，这也就意味着两个点最小割的两侧中的点的最小割互不相干，这是Gomory_tree中最重要的定理，意味着可以采用递归的方法以及一个图中的最小割最多又n-1个，这也就是本题的基本思想（还是好好研究下论文吧）
对于本题，有两种做法，第一种，只是利用上述Gomory_tree的性质方法，于是可以采用分治的策略，先求出在同一集合中的任意两点的最小割，再把在这个割两侧的点对的最小割更新，又由于上面提到的性质，可以分别递归处理，把当前集合根据割划分为两个集合递归更新
这也是网上大部分人的做法，但本人的网络流写的太屎，只能卡过luogu的数据，bzoj实在过不了（我也不知道为何，但求大犇指教）
接下来帖一波分治的代码
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define rep(i,a,b) for(i=(a);i>=(b);--i)
#define mm(a,b) memset(a,b,sizeof(a))
#define ll long long
#define inf 999999999
using namespace std;
int read(){
int fg = 1,sum = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-')fg = -1;c = getchar();}
while(c >='0' && c <='9')sum = sum*10 + c-'0',c = getchar();
return sum * fg;
}
const int maxn = 200010;
int ans[200][200] ;
int d[maxn] , Begin[maxn], to[maxn] , e, Next[maxn], w[maxn];
int n,m,fa[maxn];
void init(){
e = -1;
mm(Begin, -1);
int i , j;
For(i,1,n)fa[i] = i;
For(i,1,n){
For(j,1,n){
ans[i][j] = ans[j][i] = inf;
}
}//ans[i][j]存的是i到j的最小割
}
void add(int x,int y,int z){
to[++e] = y;
Next[e] = Begin[x];
Begin[x] = e;
w[e] = z;
}
int st, en;
bool bfs(){
queue<int> q;
while(!q.empty())q.pop();
mm(d,0);
d[st] = 1;
q.push(st);
while(!q.empty()){
int now = q.front();
q.pop();
int v;
for(int i = Begin[now]; i != -1; i = Next[i]){
if(w[i] && !d[v = to[i]]){
d[v] = d[now] + 1;
q.push(v);
}
}
}
if(!d[en])return 0;
return 1;
}
int cur[maxn];
int dfs(int h,int flow){
int i,k;
if(h == en)return flow;
if(flow==0)return 0;
int all = flow;
for(int &i = cur[h] ;i != -1;i = Next[i]){
if(w[i] && d[to[i]] == d[h] + 1 && (k = dfs(to[i], min(flow , w[i])))){
w[i] -= k;
w[i^1] += k;
flow -= k;
if(!flow)break;
}
}
return all - flow;
}
int solve(){
int tot = 0, ls;
while(bfs()){
memcpy(cur,Begin,sizeof(Begin));
while((ls = dfs(st, inf))){
tot += ls;
}
}
return tot;
}//以上是网络流
void restore(){
int i;
for(i=0;i<=e;i+=2){
w[i] = w[i] + w[i^1];w[i^1] = 0;
}
}//重置边权
int vis[maxn];
void bfs2(int h){
vis[h] = 1;
for(int i = Begin[h]; i != -1;i = Next[i]){
if(w[i^1] && !vis[to[i]]){
bfs2(to[i]);
}
}
}//其实没用这个函数
int a[maxn];
void Gomory_tree(int l,int r){
if(l == r || l > r)return ;
restore();
st = fa[l],en = fa[r];
int gross = solve();
int i,j;
For(i,1,n){
if(d[i]){//如果标记了
For(j,1,n){
if(!d[j]){//和没有标记的更新
ans[i][j] = ans[j][i] = min(ans[i][j] , gross);
}
}
}
}
mm(a,0);
int L = l , R = r;
For(i,l,r){
if(d[fa[i]]){
a[L++] = fa[i];
}
else a[R--] = fa[i];
}
For(i,l,r){
fa[i] = a[i];
}
Gomory_tree(l,L-1);Gomory_tree(R+1,r);
}
int main(){
int i,j,T;
init();
T = read();
while(T --){
n = read(),m = read();
init();
For(i,1,m){
int x = read(),y = read(),z = read();
add(x,y,z), add(y,x,0);
add(y,x,z), add(x,y,0);
}
Gomory_tree(1,n);
int query = read();
while(query --){
int nowans = 0;
int x = read();
For(i,1,n){
For(j,i+1,n){
if(ans[i][j] <= x)nowans ++;
}
}
printf("%d\n",nowans);
}
if(T)printf("\n");
}
return 0;
}
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define rep(i,a,b) for(i=(a);i>=(b);--i)
#define ll long long
#define mm(a,b) memset(a,b,sizeof(a))
#define inf 999999999
using namespace std;
const int maxn = 200010;
int vis[maxn],Begin[maxn],to[maxn],e,Next[maxn],w[maxn],cur[maxn];
int read(){
int sum = 0,fg = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-')fg = -1;c = getchar();}
while(c >= '0' && c <= '9')sum = sum*10 + c-'0',c = getchar();
return sum;
}
void init(){
mm(vis,0);
mm(Begin,-1);
e = -1;
}
void add(int x,int y,int z){
to[++e] = y;
Next[e] = Begin[x];
Begin[x] = e;
w[e] = z;
}
int d[maxn], cnt ,st, en;
bool bfs(){
queue<int> q;
mm(d,-1);
d[en] = 0;
q.push(en);
while(!q.empty()){
int now = q.front();
q.pop();
int v;
for(int i = Begin[now]; i!=-1; i = Next[i]){
if(w[i^1] && d[v = to[i]] == -1){
d[v] = d[now] + 1;
q.push(v);
}
}
}
return d[st] != -1;
}
int dfs(int h,int flow){
if(h == en)return flow;
if(flow == 0)return 0;
int k ,all = flow;
for(int &i = cur[h]; i!=-1;i = Next[i]){
if(w[i] && d[to[i]] == d[h] - 1 && (k = dfs(to[i], min(flow , w[i])))){
w[i] -= k;
w[i^1] += k;
flow -= k;
if(!flow)break;
}
}
return all - flow;
}
int solve(){
int ans = 0, ls = 0;
while(bfs()){
memcpy(cur,Begin,sizeof Begin);
while((ls = dfs(st , inf))){
ans += ls;
}
}
return ans;
}
void restore(){
for(int i = 0;i <= e; i += 2){
w[i] += w[i^1] ; w[i^1] = 0;
}
}
int fa[maxn] ,save[maxn];
void dfsdfs(int x){
vis[x] = cnt;
for(int i = Begin[x];i != -1;i = Next[i]){
if(w[i] && vis[to[i]] != cnt){
dfsdfs(to[i]);
}
}
}
void Gomory_tree(int n){
int i;
For(i,2,n)fa[i] = 1;
For(i,2,n){
restore();
st = i,en = fa[i];
// ++cnt;
save[i] = solve();int j;
// dfsdfs(i);
For(j,i+1,n){
if(d[j] == -1 && fa[i] == fa[j]){
fa[j] = i;
}
}//直接按着建树的方法模拟
}
restore();
}
int lead[maxn];
int lca(int x,int y){//求两点的LCA
++cnt;
while(1){
while(x){
if(vis[x] == cnt)return x;
vis[x] = cnt;
x = fa[x];
}
swap(x,y);
}
}
int query(int x,int y){
int ans = inf;
while(x != y){ans = min(ans , save[x]);x = fa[x];}
return ans;
}
int ask(int u,int v){
int LCA = lca(u,v);
return min(query(u,LCA),query(v,LCA));
}
int tot ;
void build(int n){
tot = 0;int i , j;
For(i,1,n){
For(j,i+1,n){
lead[++tot] = ask(i,j);
}
}
sort(lead+1,lead+tot+1);
}
int main(){
int i,j,n,m,_;
_=read();
while(_--){
init();cnt = 0;tot = 0;
n = read(),m = read();
For(i,1,m){
int x,y,z;
x = read(),y = read(),z = read();
add(x,y,z),add(y,x,0);
add(y,x,z),add(x,y,0);
}
Gomory_tree(n);
build(n);
int Q;
Q = read();
For(i,1,Q){
int x;
x = read();
int tmp = upper_bound(lead+1,lead+tot+1,x)-lead-1;
printf("%d\n",tmp);
}
if(_)printf("\n");
}
return 0;
}
因篇幅问题不能全部显示，请点此查看更多更全内容