BZOJ2521【SHOI2010】最小生成树 <最小割>

Problem

【SHOI2010】最小生成树

Time Limit: $10 Sec$
Memory Limit: $128 MB$

Description

$Secsa$最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个$n$个点、$m$条边的无向图的最小生成树有一个$Krustal$算法和另一个$Prim$的算法。另外，他还知道，某一个图可能有多种不同的最小生成树。例如，下面图 $3$中所示的都是图 $2$中的无向图的最小生成树：

![][1]

当然啦，这些都不是今天需要你解决的问题。$Secsa$想知道对于某一条无向图中的边$AB$，至少需要多少代价可以保证$AB$边在这个无向图的最小生成树中。为了使得$AB$边一定在最小生成树中，你可以对这个无向图进行操作，一次单独的操作是指：先选择一条图中的边 $P_1P_2$，再把图中除了这条边以外的边，每一条的权值都减少$1$。如图 $4$所示就是一次这样的操作：

![][2]

Input

输入文件的第一行有$3$个正整数$n$、$m$、$Lab$分别表示无向图中的点数、边数、必须要在最小生成树中出现的$AB$边的标号。
接下来$m$行依次描述标号为$1,2,3\cdots, m$的无向边，每行描述一条边。每个描述包含$3$个整数$x$、$y$、$d$，表示这条边连接着标号为$x$、$y$的点，且这条边的权值为$d$。
输入文件保证$1\le x,y\le N$,$x\ne y$,且输入数据保证这个无向图一定是一个连通图。

Output

输出文件只有一行，这行只有一个整数，即，使得标号为$Lab$边一定出现最小生成树中的最少操作次数。

Sample Input

4 6 1
1 2 2
1 3 2
1 4 3
2 3 2
2 4 4
3 4 5

Sample Output

1

HINT

样例就是问题描述中的例子。
1\le n\le 500, 1\le M\le 800,1\le D<10^6$

标签：最小割

Solution

$除边i外其他边权值-1 \iff 边i权值+1$
设$id$边连接$u,v$，以$u$为源，$v$为汇，断开$id$边，形成一个网络流图。对于此图中的任意一个割，若此割上的所有边边权均大于$id$边边权，则$id$边必在$MST$中。
于是把每条边边权变为“改变到使此边边权大于$id$边边权的代价”，即$W_{id}+1-W_{cur}$，然后跑最小割即可。

Code?

#include <bits/stdc++.h>
#define MAX_N 500
#define MAX_M 800
#define INF 0x7f7f7f7f
using namespace std;
int n, m, id, s, t, tc, cnt, pr[MAX_N+5], d[MAX_N+5];
struct node {int u, v, c, nxt;} E[MAX_M*10];
struct edge {int u, v, c, id;} e[MAX_M+5];
bool cmp(const edge &a, const edge &b) {return a.c < b.c;}
void init() {s = e[id].u, t = e[id].v, tc = e[id].c; memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pr[u], pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (!c || ~d[v])	continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t)	return flow;
    int ret = 0;
    for (int i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (!c || d[v] != d[u]+1)	continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow)	break;
    }
    if (!ret) d[u] = -1;
    return ret;
}
int Dinic() {int ret = 0;    while (BFS()) ret += DFS(s, INF);	return ret;}
int main() {
    scanf("%d%d%d", &n, &m, &id);
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c), e[i].id = i;
    init(), sort(e+1, e+m+1, cmp);
    for (int i = 1; i <= m; i++) if (e[i].id^id) {
        if (e[i].c > tc) break;
        addedge(e[i].u, e[i].v, tc-e[i].c+1);
        addedge(e[i].v, e[i].u, tc-e[i].c+1);
    }
    printf("%d", Dinic());
    return 0;
}