看大家都是倍增，我换一个简单点的方法吧。
一开始还以为是最小割的模板呢
1.题意
- 每次询问$u$到$v$的最小割。
- 有$Q$个询问，点数、边数分别为$n$、$m$。
- $Q \leq 10^5,n \leq 500,m \leq 1500$。
2.知识储备
网络流 + 最大流
最大流最小割定理
不会请移步
我的博客 或者百度
3.最小割树
很明显，不可能每次求最小割（复杂度为 $O(Qn^2m)$）。
我们将一个网络流的图转化为一棵树，其中原图 $u$ 到 $v$ 的最小割即为转化到树上。
树的一个性质是：删除一条边，树变得不连通。
那么，我们可以任意选 2 个点 $s$ 与 $t$，跑最小割（即最大流），然后再连一条从 $s$ 到 $t$ 的边。
又 Dinic 算法最后一次 bfs 相当于求一个最小割，原图就被分为了两部分。
最后分治就可以了，复杂度为 $O(n^3m)$（Dinic 跑不满的，所以不会超时）。
按这样建出的树，就是一棵无根树。
我们可以发现一个有趣的性质：$u$ 到 $v$ 的最小割就是树上从 $u$ 到 $v$ 的所有路径长的最小值。
可以感性地理解一下（ 主要是太菜不会证 ）：最小割即为最小的路径长，把 $u$ 到 $v$ 的任意一条路径切断，都是割。
注意：
每次跑 Dinic 时，都要对全图进行，否则就不是最大流
（$u$ 到 $v$ 的最大流就是针对全局的）。
Code：
1 | void work(int l,int r) |
4.处理询问
由于询问数很多（ $Q \leq 10^5$ ），很多 dalao 选择了树上倍增的做法，复杂度为 $O(Q \log n)$。
鉴于本人对倍增不太熟练，我换了一种方式。
观察题目数据范围，发现 $n$ 较小，而 $Q$ 较大，所以使用预处理的方式，先将答案处理好。
复杂度为 $O(n^2)$。
我们甚至不用建树（心中有“树”即可），在每一个 work(l,r) 函数中直接统计从 $s$ 所在集合 $S$ 到 $t$ 所在集合 $T$ 的答案。
当前 $S$ 与 $T$ 集合的连接只有 $s$ 与 $t$（其他的都在集合内部）。
则 $\forall u \in S,v \in T$，都有：
同时，由于正向与反向都相同，所以不要忘记处理反向。
最后每个询问，输出答案即可。
代码实现时，注意以下几个细节：
每一次最大流时，都要先恢复开始的网络流（即退流）。
插入网络流的边时，要双向插入（题目没有指明哪个是起点）。
- 下标从 0 开始到 $n$。
- 每一次最大流时，先保存源点和汇点，防止被覆盖（如果 $s$ 与 $t$ 使用全局变量）（
卡了一个多小时我才发现）。
其余细节看代码吧。
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
using namespace std;
const int N=505,M=6005,INF=0x3f3f3f3f;
//M要开4倍，因为正反各要2条边
int h[N],e[M],ne[M],w[M],idx;
int cur[N],q[N],d[N],S,T,n,m;
int node[N],ans[N][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,int limit)
{
if (x==T) return limit;
int 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;
}//注意退流的方式
int dinic()
{
init();
int r=0,flow;
while (bfs()) while (flow=findflow(S,INF)) r+=flow;
return r;
}//Dinic模板
void work(int l,int r)
{
if (l==r) return ;
S=node[l],T=node[l+1];
int t=dinic(),s=node[l],tt=node[l+1];//将源汇点存下来
ans[T][S]=ans[S][T]=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()
{
memset(h,-1,sizeof h);
memset(ans,0x3f,sizeof ans);
cin>>n>>m;
int x,y,z;
while (m--)
{
scanf("%d %d %d",&x,&y,&z);
add(x,y,z);add(y,x,z);//双向边
}
for (int i=0;i<=n;++i) node[i]=i;
work(0,n);//下标从0开始
int que;cin>>que;
while (que--)
{
scanf("%d %d",&x,&y);
printf("%d\n",ans[x][y]);
}
return 0;
}