最小割树,就是字面上的意思,用来求点对的最小割。

引理:对于任意两点$u,v$,最小割为$cut(x,y)$。把$u$通过剩余网络能到达的点集称为$U$,$v$能到达的点积称为$V$。$\forall x\in U,y\in V,cut(x,y)\le cut(u,v)$。

证明:若$cut(x,y)>cut(u,v)$,意味着$u,v$的最小割$cut(x,y)$无法把$U,V$割开,即仍存在增广路可以由$u$到$y$,因此原命题得证。

定理:对于$a,b,c$,其中$c$是$a,b$路径上的一点,$cut(a,b)\ge \min\{cut(a,c),cut(b,c)\}$。

证明:

考虑$cut(a,b)$最小。

讨论c在删掉(a,b)的割边后与a还是与b联通,不妨设与b,同理可得另一种。

由引理1:$cut(a,c)\le cut(a,b)$

根据假设,$cut(a,b)\le cut(a,c)$,因此$cut(a,b)=cut(a,c)$

同样地,若$c$与$a$相通,可以得到$cut(a,b)=cut(b,c)$

另外两个同理。

从此可以发现一个规律:三个中,必定有两个较小的,且这两个小的相等。

那么自然,$cut(a,b)\ge \min\{cut(a,c),cut(b,c)\}$成立。

推论:对于两点$x,y$,其路径上的点$w_i$,

$cut(x,y)\ge \min\{cut(x,w_1),cut(w_1,w_2),\cdots,cut(w_k,y)\}$

根据推论,$cut(p,q)=\min\{cut(x,w_1),cut(w_1,w_2),\cdots,cut(w_k,y)\}$。

由于$x$在$p$这一侧,$y$在$q$这一侧,实际上将$p,q$割成两个点集$U,V$,$x,y$分处不同点集,则可以用引理:

$cut(x,y)\le cut(p,q)$

因此$cut(x,y)=cut(p,q)$,即$x,y$的最小割为$x,y$在最小割树路径的最小边权。

因此实现流程就是任意选两个点,做最小割,把点分成两个集合,继续进行递归。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=855,M=8555;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int n,m,col[N],tot;
namespace ISAP
{
    struct node{int x,y,c;}e[M];
    struct edge{int y,c,next;}a[M<<1];int len,last[N];
    void ins(int x,int y,int c)
    {
        a[++len]=(edge){y,c,last[x]};last[x]=len;
        a[++len]=(edge){x,c,last[y]};last[y]=len;
    }
    void init()
    {
        qr(n),qr(m);++n;
        for(int i=1;i<=m;i++)qr(e[i].x),qr(e[i].y),qr(e[i].c),e[i].x++,e[i].y++;
    }
    int d[N],gap[N],q[N],s,t,cur[N];
    void bfs()
    {
        len=1;memset(last,0,sizeof(last));
        for(int i=1;i<=m;i++)ins(e[i].x,e[i].y,e[i].c);memcpy(cur,last,sizeof cur);
        memset(gap,0,sizeof(gap));memset(d,0,sizeof(d));++gap[d[t]=1];
        int l=1,r=1;q[1]=t;
        for(int x=q[l],y,k;l<=r;x=q[++l])for(k=last[x];k;k=a[k].next)if(!d[y=a[k].y])q[++r]=y,++gap[d[y]=d[x]+1];
    }
    int flow(int x,int f)
    {
        if(x==t)return f;
        int sum=0,tmp;
        for(int y,&k=cur[x];k;k=a[k].next)if(d[y=a[k].y]+1==d[x])
        {
            sum+=(tmp=flow(y,min(a[k].c,f)));
            a[k].c-=tmp;a[k^1].c+=tmp;f-=tmp;
            if(!f)return sum;
        }
        if(!(--gap[d[x]]))d[s]=n+1;
        ++gap[++d[x]];cur[x]=last[x];
        return sum;
    }
    int maxflow(int x,int y)
    {
        s=x,t=y;int ans=0;
        bfs();
        while(d[s]<=n)
            ans+=flow(s,1e9);
        return ans;
    }
    void get_col(int x)
    {
        col[x]=tot;
        for(int k=last[x],y;k;k=a[k].next)
            if(a[k].c&&col[y=a[k].y]!=tot)get_col(y);
    }
}
namespace GHTree
{
    struct edge{int y,d,next;}a[N<<1];int last[N],len;
    void ins(int x,int y,int d){a[++len]=(edge){y,d,last[x]};last[x]=len;}
    int sta[N],p[N],d[N][N];
    void init(){for(int i=1;i<=n;i++)p[i]=i;}
    void build(int l,int r)
    {
        if(l==r)return ;
        int x=p[l],y=p[l+1];
        int cut=ISAP::maxflow(x,y);
        ins(x,y,cut);ins(y,x,cut);++tot;
        ISAP::get_col(x);int L=l,R=r;
        for(int i=l;i<=r;i++)
            if(col[p[i]]==tot)sta[L++]=p[i];
            else sta[R--]=p[i];
        for(int i=l;i<=r;i++)p[i]=sta[i];
        build(l,L-1);build(R+1,r);
    }
    void dfs(int s,int x,int mn)
    {
        d[s][x]=mn;
        for(int k=last[x],y;k;k=a[k].next)
            if(d[s][y=a[k].y]==-1)dfs(s,y,min(mn,a[k].d));
    }
    void solve()
    {
        init();
        build(1,n);
        memset(d,-1,sizeof(d));
        for(int i=1;i<=n;i++)dfs(i,i,0x3f3f3f3f);
        int q;qr(q);
        while(q--)
        {
            int x,y;qr(x),qr(y);++x,++y;
            qw(d[x][y]);puts("");
        }
    }
}
int main()
{
    ISAP::init();
    GHTree::solve();
    return 0;
}