bzoj 2521 [Shoi2010]最小生成树

Description

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

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

Input

输入文件的第一行有3个正整数n、m、Lab分别表示无向图中的点数、边数、必须要在最小生成树中出现的AB边的标号。
接下来m行依次描述标号为1,2,3…m的无向边，每行描述一条边。每个描述包含3个整数x、y、d，表示这条边连接着标号为x、y的点，且这条边的权值为d。
输入文件保证1<=x,y<=N,x不等于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个样例就是问题描述中的例子。

1<=n<=500,1<=M<=800,1<=D< 10^6

题解

操作相当于对一个边+1。

我们发现只要别的边的大小比这条边还大的话，那就不需要考虑它的影响了。

如果想排除某条边的干扰，显然让他的权值比给定边恰好大1是最优的选择。

所以我们可以把所有小于等于他权值的边加入网络流的图中，权值改为wid(给定边的权值)-当前边的权值+1，然后以给定边的两个端点为起点终点跑最大流求最小割即可，因为我们需要求最小的代价使给定边的两个端点不联通。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define M 20100
#define N 10100
using namespace std;
const int inf = 0x3f3f3f3f;
struct flows {
    struct node {
        int to, next, flow;
    } e[M];
    int tot, st[N], dis[N], cur[N];
    void init() {
        tot = -1, memset(e, -1, sizeof e),
        memset(st, -1, sizeof st);
    }
    void add(int x, int y, int z) {
        e[++tot].to = y;
        e[tot].flow = z;
        e[tot].next = st[x];
        st[x] = tot;
    }
    void add_edge(int x, int y, int z) {
//      printf("%d %d %d\n", x, y, z);
        add(x, y, z), add(y, x, 0);
        add(x, y, 0), add(y, x, z);
    }
    queue <int> que;
    int bfs(int S, int T) {
        memcpy(cur, st, sizeof st);
        memset(dis, 0, sizeof dis);
        while (!que.empty()) que.pop();
        que.push(S);
        dis[S] = 1;
        while(!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = st[now]; ~i; i = e[i].next)
                if (e[i].flow && !dis[e[i].to]) {
                    dis[e[i].to] = dis[now] + 1;
                    if (e[i].to == T) return 1;
                    que.push(e[i].to);
                }
        }
        return 0;
    }
    int finds(int now, int T, int flow) {
        if (now == T)
            return flow;
        int f;
        for (int i = cur[now]; ~i; i = e[i].next) {
            cur[now] = i;
            if (e[i].flow && dis[e[i].to] == dis[now] + 1 &&
                (f = finds(e[i].to, T, min(flow, e[i].flow)))) {
                e[i].flow -= f;
                e[i^1].flow += f;
                return f;
            }
        }
        return 0;
    }
    int dinic(int S, int T) {
        int flow = 0, x;
        while(bfs(S, T)) {
            while(x = finds(S, T, inf)) {
                flow += x;
            }
        }
        return flow;
    }
}flow;
struct edge {
    int to, next, val, from;
}e[M];
int st[N], tot;
void add(int x, int y, int z) {
    e[++tot].to = y;
    e[tot].next = st[x];
    e[tot].from = x;
    e[tot].val = z;
    st[x] = tot;
}
bool comp(edge a, edge b) {
    return a.val < b.val;
}
int n, m, t, fr, to, va, x, y, z;
main() {
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d%d", &x, &y, &z),
        add(x, y, z);
    flow.init();
    for (int i = 1; i <= tot; ++i)
        if (e[i].val <= e[t].val && i != t)
            flow.add_edge(e[i].from, e[i].to, e[t].val - e[i].val + 1);
    int S = e[t].from, T = e[t].to;
    printf("%d\n", flow.dinic(S, T));
}