Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

最小割树

Posted on Edited on

考试时再一次撞到了，依旧不会，爆蛋（小编不理解啊）

简介

先看看它是干什么的：将一个无向图转化成树，满足树上任意两点的最小割等于原图的最小割。

抄抄定义：

1
定义一棵树T为最小割树，如果对于树上的所有边(s,t)，树上去掉(s,t)后产生的两个集合恰好是原图上(s,t)的最小割把原图分成的两个集合，且边(u,v)的权值等于原图上(u,v)的最小割

这时我们就需要构造最小割树，我们得知 $dinic$ 的最后一次增广会以最小割的代价将图割开，此时 我们考虑分治：

​

定义 $val[x][y]$ 为 $x$ 和 $y$ 之间的最小割。

可以发现，$val[x][y] = min(min(val[x][S],val[S][T]),val[T][y])$。证明据巨佬说不显然，有兴趣的童鞋可以上网查一查。

之后就可以在当前点集随意选取两个点 $u,v$，在原图上跑出他们之间的最小割，然后就在树上连一条从 $u$ 到 $v$,权值为 $val[u][v]$的边，之后递归处理即可。

时间复杂度：$O(n^3m)$ 然而根本跑不满。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 500 + 5, M = 6000 + 5, Inf = 1e9 + 7;
int n, m;
namespace flow{
    int idx = 1;
    int e[M], ne[M], h[N];
    int w[M];
    int S, T;
    inline void add(int x, int y, int z)
    {
        idx ++;
        e[idx] = y, ne[idx] = h[x], h[x] = idx, w[idx] = z;
    }
    inline void addage(int x, int y, int z)
    {
        add(x, y, z), add(y, x, 0);
    }
    int depth[N], now[N];
    bool bfs()
    {
        memset(depth, 0, sizeof(depth));
        memcpy(now, h, sizeof(h));
        depth[S] = 1;
        queue<int>q;
        q.push(S);
        while(!q.empty())
        {
            int o = q.front(); q.pop();
            for(int i = h[o]; ~i;i = ne[i])
            {
                int j = e[i];
                if(depth[j] || !w[i]) continue;
                depth[j] = depth[o] + 1;
                if(T == j) return true;
                q.push(j);
            }
        }
        return false;
    }
    int dfs(int x, int last)
    {
        if(x == T || !last) return last;
        int rest = last, k;
        for(int i = now[x]; ~i && rest;i = ne[i])
        {
            int j = e[i];
            now[x] = i;
            if(depth[j] == depth[x] + 1 && w[i])
            {
                k = dfs(j, min(w[i], rest));
                if(!k) 
                {
                    depth[j] = 0;
                    continue;
                }
                w[i] -= k;
                w[i ^ 1] += k;
                rest -= k;
            }
        }   
        return last - rest;
    }
    void init()
    {
        for(int i = 2;i <= idx;i += 2)
        {
            w[i] += w[i ^ 1];
            w[i ^ 1] = 0;
        }
    }
    int dinic(int s, int t)
    {
        init();
        S = s, T = t;
        int ans = 0, res = 0;
        while(bfs())
            while(res = dfs(S, Inf)) ans += res;
        return ans;
    }
}
int ans[N][N];
namespace Seg{
    int id[N];
    int q[N], p[N];
    int idx = 1;
    int e[M], ne[M], h[N], w[M];
    void add(int x, int y, int z)
    {
        idx ++;
        e[idx] = y, ne[idx] = h[x], h[x] = idx, w[idx] = z;
    }
    void addage(int x, int y, int z)
    {
        add(x, y, z), add(y, x, z);
    }
    void build(int l, int r)
    {
        if(l == r) return ;
        int num = flow:: dinic(id[l], id[r]), st = id[l], ed = id[r];
        ans[id[l]][id[r]] = ans[id[r]][id[l]] = num;
        int hh = 0, tt = 0;
        for(int i = l;i <= r;i ++)
        {
            if(flow:: depth[id[i]]) q[++ hh] = id[i];
            else p[++ tt] = id[i];
        }
        for(int i = 1;i <= hh;i ++) id[i + l - 1] = q[i];
        for(int i = 1;i <= tt;i ++) id[i + hh + l - 1] = p[i];
        build(l, l + hh - 1);
        build(l + hh, r);
        for(int i = 1;i <= hh;i ++)
            for(int j = 1, o, u;j <= tt;j ++)
            {
                o = id[i + l - 1], u = id[j + hh + l - 1];
                ans[o][u] = ans[u][o] = min(min(ans[o][st], ans[st][ed]), ans[ed][u]);
            }
    }
}
int main()
{
    memset(ans, 0x3f, sizeof(ans));
    memset(flow:: h, -1, sizeof(flow:: h));
    scanf("%d%d", &n, &m);
    for(int i = 1, o, u, z;i <= m;i ++)
    {
        scanf("%d%d%d", &o, &u, &z);
        flow:: addage(o, u, z);
        flow:: addage(u, o, z);
    }
    for(int i = 0;i <= n;i ++) Seg:: id[i] = i;
    Seg:: build(0, n);
    int q;
    scanf("%d", &q);
    while(q --)
    {
        int o, u;
        scanf("%d%d", &o, &u);
        printf("%d\n", ans[o][u]);
    }
    return 0;
}