BZOJ 1937 - [Shoi2004]Mst 最小生成树

#费用流 #KM
Published on 2016-06-22

题目地址

描述

分析

根据贪心，树边的权只能减小，非树边的权只能增加，不妨设边 ii 的改变量为 did_i。
则根据最小生成树的性质，如果有一条非树边 (x,y,wi)(x, y, w_i)，那么树上 x→yx \rightarrow y 的路径上，所有的边均小于等于 wiw_i，也就是：

wi+di≥wj−dj,j∈x→yw_i + d_i \ge w_j - d_j, j\in x\rightarrow y

移项可得：

wj−wi≤di+dj,j∈x→yw_j - w_i \le d_i + d_j, j\in x\rightarrow y

这正是 Kuhn-Munkres算法 中的顶标约束！我们要寻找最小的一组顶标和，满足所有的约束。
最小的顶标和，也就是最大权完美匹配的值，我们考虑建图：
将边化为点，按照刚刚的方法从非树边到树路径上的树边连边 wi−wjw_i - w_j，同时默认非树边到树边之间均有一条权值为 0 的边（保证有完美匹配）。

也可使用费用流，为了避免边过多，我们不加入权值为 0 的边，转而求解最大权可行流（一旦距离为负就停止增广）。

代码

//  Created by Sengxian on 6/22/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1937 KM 顶标
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}
const int maxn = 50 + 3, maxm = 800 + 3, INF = 0x3f3f3f3f;

namespace MCMF {
    const int maxNode = maxm + 10;
    struct edge {
        int to, cost, cap, rev;
        edge(int to, int cost, int cap, int rev): to(to), cost(cost), cap(cap), rev(rev) {}
    };
    vector<edge> G[maxNode];
    void addEdge(int f, int t, int cost, int cap) {
        G[f].push_back(edge(t, cost, cap, G[t].size()));
        G[t].push_back(edge(f, -cost, 0, G[f].size() - 1));
    }
    int dis[maxNode], preve[maxNode], prevv[maxNode];
    bool inq[maxNode];
    int maxCostFlow(int s, int t) {
        int ans = 0;
        while (true) {
            memset(dis, -INF, sizeof dis);
            int ff = dis[0];
            memset(inq, 0, sizeof inq);
            dis[s] = 0;
            queue<int> q;
            q.push(s);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                inq[u] = false;
                for (int i = 0; i < (int)G[u].size(); ++i) {
                    const edge &e = G[u][i];
                    if (e.cap && dis[e.to] < dis[u] + e.cost) {
                        dis[e.to] = dis[u] + e.cost;
                        prevv[e.to] = u, preve[e.to] = i;
                        if (!inq[e.to]) inq[e.to] = true, q.push(e.to);
                    }
                }
            }
            if (dis[t] == ff) break;
            int d = INF;
            for (int u = t; u != s; u = prevv[u]) d = min(d, G[prevv[u]][preve[u]].cap);
            if (d * dis[t] <= 0) break;
            ans += d * dis[t];
            for (int u = t; u != s; u = prevv[u]) {
                edge &e = G[prevv[u]][preve[u]];
                e.cap -= d, G[e.to][e.rev].cap += d;
            }
        }
        return ans;
    }
}

int n, m;

int G[maxn][maxn], id[maxn][maxn], prevv[maxn];
bool tree[maxn][maxn];

void dfs(int u, int fa = -1) {
    for (int v = 0; v < n; ++v) if (tree[u][v] && v != fa) {
        prevv[v] = u;
        dfs(v, u);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt();
    memset(G, INF, sizeof G);
    memset(tree, 0, sizeof tree);
    for (int i = 0; i < m; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1, c = ReadInt();
        G[f][t] = G[t][f] = c;
        id[f][t] = id[t][f] = i;
    }
    int S = m, T = m + 1;
    for (int i = 0; i < n - 1; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1;
        tree[f][t] = tree[t][f] = true;
        MCMF::addEdge(S, id[f][t], 0, 1);
    }
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) if (G[i][j] != INF && !tree[i][j]) {
            MCMF::addEdge(id[i][j], T, 0, 1);
            dfs(i);
            for (int u = j; u != i; u = prevv[u]) {
                assert(tree[prevv[u]][u]);
                if (G[prevv[u]][u] - G[i][j] > 0) MCMF::addEdge(id[prevv[u]][u], id[i][j], G[prevv[u]][u] - G[i][j], 1);
            }
        }
    printf("%d\n", MCMF::maxCostFlow(S, T));
    return 0;
}
BZOJ 2438 - [中山市选2011]杀人游戏