最小割相关

(Updated: )
(9 mins to read)

最小割的方案

跑一遍最大流，记录从s出发能到达的点集S，不能到达的点集为T，则跨越S和T的满流边（残留网络中容量=0）是最小割中的边

可行边与必须边

可行边：属于所有可能的最小割集的并集中的边必须边：属于所有可能的最小割集的交集中的边跑一遍最大流，然后对残余网络（容量大于0的边）跑一遍tarjan如果该边还有容量，不属于最小割集，所以既不是可行边也不是必须边如果某条边连接的两个点分属于两个scc，则为可行边如果某条边连接的两个点一个与S同在一个scc，一个与T同在一个scc，则为必须边

求边数最少的最小割

设原图总边数=M让原图的每一条边的权值w变成$(M+1)w+1$再跑最大流即可

每条边有两个权值，在最小化第一个权值的割后，找一个第二个权值字典序最小的割

先随便求一个最小割，将这些边按照第二个权值排序，判断该边是否是可行边，如果是就选择，割掉一条边需要利用退流操作，具体做法是对于边(u,v)，让u向S跑一遍最大流，再让T向v跑一遍最大流，最后让(u,v)这条边及其反边的残余流量置0，即w=0

最小割树

求任意两点间的最小割本质只有$O(n)$种，建出最小割树后，u，v两点的最小割等于路径上的最小边权建树方法：跑n次最大流每次随机取两个点，求它们的最小割，将图分为两部分，在这两个集合间连一条边权为最小割的边，然后分治处理两个集合。这样最后会得到一棵树。则两个点之间的最小割大小为其树上唯一路径的最小值。每次网络流的流量要复原，所以用变量fw记录每条边已经流过的流量，变量w记录容量保持不变，当fw=w时说明该边满流，复原只需要清零fw即可求路径最小值没必要倍增，因为点数不会很大，直接建出树，以每个点为根bfs一次即可

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
const int N = 505, M = 2e3 + 5;
int n, m;
int cnt, head[N];
struct node
{
  int next, to, w, fw;
}e[M<<1];
inline void add(int u, int v, int w)
{
  e[++cnt] = {head[u], v, w, 0};
  head[u] = cnt;
}
struct Dinic
{
  int n, m, s, t;
  int dep[N], cur[N];
  void init(int n)
  {
    this->n = n;
    cnt = 1, m = 0;
    memset(head,0,(n+1)*sizeof(int));
  }
  void addedge(int u,int v,int cap)
  {
    add(u, v, cap);
    add(v, u, cap);
    m += 2;
  }
  bool bfs()
  {
    memset(dep,0,(n+1)*sizeof(int));
    memcpy(cur,head,(n+1)*sizeof(int));
    queue <int> q;
    q.push(s); dep[s] = 1;
    while(!q.empty())
    {
      int u = q.front(); q.pop();
      for(int i=head[u];i;i=e[i].next)
      {
        int v = e[i].to;
        if(!dep[v]&&e[i].fw<e[i].w)
        {
          dep[v] = dep[u] + 1;
          q.push(v);
        }
      }
    }
    return dep[t];
  }
  int dfs(int u,int flow)
  {
    if(u==t||!flow) return flow;
    int used = flow;
    for(int i=cur[u];i;i=e[i].next)
    {
      cur[u] = i;
      int v = e[i].to;
      if(dep[v]==dep[u]+1)
      {
        int low = dfs(v,min(flow,e[i].w-e[i].fw));
        e[i].fw += low; e[i^1].fw -= low;
        flow -= low;
        if(!flow) break;
      }
    }
    return used - flow;
  }
  int go(int x, int y)
  {
    int maxflow = 0; s = x, t = y;
    for(int i=2; i<=cnt; i++) e[i].fw = 0;
    while(bfs()) maxflow += dfs(s,INF);
    return maxflow;
  }
}MF;
struct GHT
{
  int pt[N], col[N], tmpt[N], cnt, cut[N][N];
  vector<pii> G[N];
  void dfs(int u)
  {
    col[u] = cnt;
    for(int i=head[u]; i; i=e[i].next)
      if(e[i].fw<e[i].w && col[e[i].to]!=cnt)
        dfs(e[i].to);
  }
  void build(int l, int r)
  {
    if(l>=r) return;
    int x = pt[l], y = pt[l+1];
    int cutw = MF.go(x, y);
    ++cnt; dfs(x); int p = l, q = r;
    for(int i=l; i<=r; i++)
      if(col[pt[i]]==cnt) tmpt[p++] = pt[i];
      else tmpt[q--] = pt[i];
    for(int i=l; i<=r; i++) pt[i] = tmpt[i];
    G[x].pb({y, cutw}); G[y].pb({x, cutw});
    build(l, p-1); build(q+1, r);
  }
  void bfs(int s, int *dis)
  {
    for(int i=1; i<=n; i++) dis[i] = -1;
    dis[s] = INF;
    queue<int> q; q.push(s);
    while(sz(q))
    {
      int u = q.front(); q.pop();
      for(auto it : G[u])
      {
        int v = it.fi, w = it.se;
        if(~dis[v]) continue;
        dis[v] = min(dis[u], w);
        q.push(v);
      }
    }
  }
}T;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  MF.init(n);
  for(int i=1; i<=m; i++)
  {
    int u, v, w;
    cin >> u >> v >> w;
    MF.addedge(u, v, w);
  }
  iota(T.pt+1, T.pt+n+1, 1);
  T.build(1, n);
  for(int i=1; i<=n; i++) T.bfs(i, T.cut[i]);
  int q; cin >> q;
  while(q--)
  {
    int u, v;
    cin >> u >> v;
    cout << T.cut[u][v] << '\n';
  }
  return 0;
}