[BZOJ2561]最小生成树 题解

[BZOJ2561]最小生成树 题解

题目地址:BZOJ:Problem 2561. — 最小生成树

题目描述

给定一个边带正权的连通无向图G=(V,E),其中N=|V|,M=|E|,N个点从1到N依次编号,给定三个正整数u,v,和L (u≠v),假设现在加入一条边权为L的边(u,v),那么需要删掉最少多少条边,才能够使得这条边既可能出现在最小生成树上,也可能出现在最大生成树上?

输入输出格式

输入格式:
第一行包含用空格隔开的两个整数,分别为N和M;
接下来M行,每行包含三个正整数u,v和w表示图G存在一条边权为w的边(u,v)。
最后一行包含用空格隔开的三个整数,分别为u,v,和 L;
数据保证图中没有自环。

输出格式:
输出一行一个整数表示最少需要删掉的边的数量。

输入输出样例

输入样例#1:

3 2
3 2 1
1 2 3
1 2 2

输出样例#1:

1

说明

对于20%的数据满足N ≤ 10,M ≤ 20,L ≤ 20;
对于50%的数据满足N ≤ 300,M ≤ 3000,L ≤ 200;
对于100%的数据满足N ≤ 20000,M ≤ 200000,L ≤ 20000。

题解

回想一下最小生成树是怎么来找的,以Kruskal算法为例。我们考虑边权 < L的边,这些边如果能够使u和v连通,则我们想加进去的(u, v, L)这条边就没法加入最小生成树了,因此我们需要删掉一些边权 < L的边,使得u和v不能连通。这个可以用最小割来实现。最大生成树同理。由于我们删掉的边中一些是< L的一些是> L的,这两个集合并无交集,因此不需要去重,直接跑两遍最小割把答案加起来就好。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 20005, MAXM = 400005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXM << 1];
int head[MAXN], tot;

inline void reset() {
    memset(head, -1, sizeof(head)); tot = 0;
}

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int level[MAXN];
std::queue<int> que;

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    level[s] = 0; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];
bool vis[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || !left) 
        return left;
    int flow = 0; vis[u] = true;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(gra[i].cap > 0 && !vis[v] && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                left -= d; flow += d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(!left) {
                    level[u] = -1;
                    return flow;
                }
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memset(vis, 0, sizeof(vis));
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) {
            flow += f;
        }
    }
    return flow;
}

int n, m, u, v, w;

struct EData {
    int u, v, w;
} edges[MAXM];

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        edges[i].u = readint(); edges[i].v = readint(); edges[i].w = readint();
    }
    u = readint(); v = readint(); w = readint();
    int ans = 0;
    reset();
    for(int i = 1; i <= m; i++) {
        if(edges[i].w < w) {
            addedge(edges[i].u, edges[i].v, 1);
            addedge(edges[i].v, edges[i].u, 1);
        }
    }
    ans += dinic(u, v);
    reset();
    for(int i = 1; i <= m; i++) {
        if(edges[i].w > w) {
            addedge(edges[i].u, edges[i].v, 1);
            addedge(edges[i].v, edges[i].u, 1);
        }
    }
    ans += dinic(u, v);
    printf("%d", ans);
    return 0;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据