bzoj2561 最小生成樹

題意：給你無向圖，給定一條邊，求至少在原圖中刪去多少邊才能使它同時在某個最大生成樹和某個最小生成樹中。

解：

假裝我們把邊排序了，然后把所有邊權小于給定邊的邊都加進去了。

那么我們要刪的就是s到t的一個割。

最大同理。

然后我們做兩遍最小割即可。

注意邊權與給定邊相等的邊直接忽略。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
 
const int N = 20010, M = 1000010, INF = 0x3f3f3f3f;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
 
struct Edge {
    int nex, v, c;
}edge[M << 1]; int top = 1;
 
struct Eg {
    int u, v, len;
    inline bool operator <(const Eg &w) const {
        return len < w.len;
    }
}eg[M];
 
int e[N], d[N];
std::queue<int> Q;
 
inline void add(int x, int y, int z) {
    top++;
    edge[top].v = y;
    edge[top].c = z;
    edge[top].nex = e[x];
    e[x] = top;
 
    top++;
    edge[top].v = x;
    edge[top].c = z;
    edge[top].nex = e[y];
    e[y] = top;
    return;
}
 
inline bool BFS(int s, int t) {
    memset(d, 0, sizeof(d));
    d[s] = 1;
    Q.push(s);
    while(!Q.empty()) {
        int x = Q.front();
        Q.pop();
        for(int i = e[x]; i; i = edge[i].nex) {
            int y = edge[i].v;
            if(!edge[i].c || d[y]) {
                continue;
            }
            d[y] = d[x] + 1;
            Q.push(y);
        }
    }
    return d[t];
}
 
int DFS(int x, int t, int maxF) {
    if(x == t) {
        return maxF;
    }
    int ans = 0;
    for(int i = e[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(!edge[i].c || d[x] + 1 != d[y]) {
            continue;
        }
        int temp = DFS(y, t, std::min(edge[i].c, maxF - ans));
        if(!temp) {
            d[y] = INF;
        }
        ans += temp;
        edge[i].c -= temp;
        edge[i ^ 1].c += temp;
        if(ans == maxF) {
            break;
        }
    }
    return ans;
}
 
inline int solve(int s, int t) {
    int ans = 0;
    while(BFS(s, t)) {
        ans += DFS(s, t, INF);
    }
    return ans;
}
 
int main() {
    int n, m, L, s, t;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d", &eg[i].u, &eg[i].v, &eg[i].len);
    }
    scanf("%d%d%d", &s, &t, &L);
    std::sort(eg + 1, eg + m + 1);
    int i;
    for(i = 1; i <= m; i++) {
        if(eg[i].len == L) {
            break;
        }
        add(eg[i].u, eg[i].v, 1);
    }
    int ans = solve(s, t);
    memset(e, 0, sizeof(e));
    top = 1;
    for(; i <= m; i++) {
        if(eg[i].len == L) {
            continue;
        }
        add(eg[i].u, eg[i].v, 1);
    }
    printf("%d", ans + solve(s, t));
    return 0;
}

一開始我想把兩遍最小割合成一遍，后來發現不行。

比如這個樣例：

3 2 1 2 1 2 3 3 1 3 2

最小刪邊是0，但是一次最小割是1。

思考：會不會有這種情況：你刪掉一個比給定邊小的邊，使得最大生成樹無法達成(圖不連通)？

應該不會，因為你兩次割的互不影響，且都成環。