OI

BZOJ 4519: [Cqoi2016]不同的最小割

Description

学过图论的同学都知道最小割的概念：对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割。

而对冲刺NOI竞赛的选手而言，求带权图中两点的最小割已经不是什么难事了。我们可以把视野放宽，考虑有N个点的无向连通图中所有点对的最小割的容量，共能得到N(N−1)/2个数值。

这些数值中互不相同的有多少个呢？这似乎是个有趣的问题。

Input

输入文件第一行包含两个数N，M，表示点数和边数。接下来M行，每行三个数u，v，w，

表示点u和点v（从1开始标号）之间有条边权值是w。

1<=N<=850 1<=M<=8500 1<=W<=100000

Output

输出文件第一行为一个整数，表示个数。

Sample Input

4 4

1 2 3

1 3 6

2 4 5

3 4 4

Sample Output

3

Solution

大家来感受一下蒟蒻的心理阴影面积。。。

原来是求最小割的时候vis数组没有全搞成0。。。(╯‵□′)╯︵┻━┻本以为把区间l,r的搞成0就可以，然而发现这样有些路径会被之前的vis“堵死”。

大体就是Gusfield算法，不断分治来搞。

来膜拜一下神犇fhq666的blog。。。

发现这题建边的时候可以把反向边的流量置为w。。。以前没遇到过，记录一下~

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
116
117
118
119
120

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
int A[20005], B[20005];
struct edge_type {
    int to, next, r;
} edge[500005];
int S, T, cnte = 1, h[20005], d[20005], cur[20005], n, m;
bool vis[20005];
int Q[20005], tail, head, C[20005];
void ins(int u, int v, int f) {
    edge[++cnte].to = v;
    edge[cnte].next = h[u];
    edge[cnte].r = f;
    h[u] = cnte;
    edge[++cnte].to = u;
    edge[cnte].next = h[v];
    edge[cnte].r = f;
    h[v] = cnte;
}
bool bfs() {
    tail = head = 0;
    for (int i = 1; i <= n; ++i) d[i] = -1;
    Q[tail++] = S;
    d[S] = 0;
    int now;
    while (head < tail) {
        now = Q[head++];
        for (int i = h[now]; i; i = edge[i].next) {
            if (d[edge[i].to] == -1 && edge[i].r) {
                d[edge[i].to] = d[now] + 1;
                Q[tail++] = edge[i].to;
            }
        }
    }
    return d[T] != -1;
}
int dfs(int now, int a) {
    if (T == now || a == 0) return a;
    int ret = 0, f;
    for (int &i = cur[now]; i; i = edge[i].next) {
        if (d[edge[i].to] != d[now]+1) continue;
        if (f = dfs(edge[i].to, min(a, edge[i].r))) {
            a -= f;
            ret += f;
            edge[i].r -= f;
            edge[i^1].r += f;
            if (a == 0) break;
        }
    }
    if (ret == 0) d[now] = -1;
    return ret;
}
void DFS(int now) {
    vis[now] = 1;
    for (int i = h[now]; i; i = edge[i].next) {
        if (edge[i].r == 0 || vis[edge[i].to])
            continue;
        DFS(edge[i].to);
    }
}
int ptr;
void init() {
    for (int i = 2; i <= cnte; i += 2)
        edge[i].r = edge[i^1].r = (edge[i].r + edge[i^1].r) >> 1;
}
void mincut(int l, int r) {
    if (l >= r) return;
    S = A[l]; T = A[r];
    init();
    int flow = 0;
    while (bfs()) {
        for (int i = 1; i <= n; ++i)
            cur[i] = h[i];
        flow += dfs(S, INF);
    }
    C[ptr++] = flow;
    for (int i = 1; i <= n; ++i)
        vis[A[i]] = 0;
    DFS(S);
    int L = l, R = r;
    for (int i = l; i <= r; ++i) {
        if (vis[A[i]]) {
            B[L++] = A[i];
        } else {
            B[R--] = A[i];
        }
    }
    for (int i = l; i <= r; ++i)
        A[i] = B[i];
    mincut(l, L - 1);
    mincut(R + 1, r);
}
int main() {
	n = getint(); m = getint();
    for (int i = 1; i <= n; ++i)
        A[i] = i;
    int x, y, z;
    for (int i = 1; i <= m; ++i) {
		x = getint(); y = getint(); z = getint();
        ins(x, y, z);
    }
    mincut(1, n);
    sort(C, C+ptr);
    int ans = 1;
    for (int i = 1; i < ptr; ++i)
        if (C[i] != C[i-1])
            ++ans;
    printf("%d", ans);
    return 0;
}