UVa11865 Stream My Contest

题目链接

   UVA - 11865 Stream My Contest

题意

   你需要花费不超过cost元来搭建一个比赛网络。网络中有n台机器，编号为0~n-1，其中机器0为服务器，其他机器为客户机。一共有m条可以使用的网线，其中第i条网线的发送端是机器$u_i$，接受端是机器$v_i$（数据只能从机器$u_i$单向传输到机器$v_i$），带宽是$b_i$ Kbps，费用是$c_i$元。每台客户机应当恰好从一台机器接受数据（即恰好有一条网线的接收端是该机器），而服务器不应从任何机器接收数据。你的任务是最大化网络中的最小带宽。

输入格式

   输入第一行为数据组数T（T≤50）。每组数据第一行为3个整数n, m, cost（1≤n≤60，1≤m≤10 000，1≤cost≤$10^9$）。以下m 行每行用4 个整数u, v, b, c（0≤u,v＜n，1≤b,c≤$10^6$，u!=v）描述一条网线。

输出格式

   对于每组数据，输出最小带宽的最大值。如果无法搭建网络，输出“streaming not possible.”（不含引号）。

分析

   二分答案（最小带宽），找出从0出发的最小树形图（需要禁用带宽小于答案的网线），判断权值和是否超过cost即可。
   固定根的最小树形图可以用朱-刘算法（也称 Edmonds 算法）解决，其时间复杂度为$O(VE)$，此算法不能找出最小树形图的各条边，只能求出其权值和。
   Tarjan提出了一种能够在$O(E+VlogV)$时间内解决最小树形图问题的算法，不过其内部实现比较复杂。

朱-刘算法

0. 初始化权值和$ans=0$
1. 给所有非根结点$v_i$选择一条权最小的入边（自环边除外），$pre[v_i]$记录其起点，$w[v_i]$记录其最小边权。如果有孤立结点（无入边），说明最小树形图不存在，算法终止。
2. 对每个结点$v_i$，将其边权累加入答案$ans=ans+w[v_i]$。
3. 检查选定的这些入边是否形成了环，有则执行步骤4，否则说明已经求出了最小树形图的权值和，结束。
4. 将每个环缩成一个点$k_i$并对环内的点重新编号$id[v_i]=k_i$，为了便于统一处理，可以对不构成环的那些点也像这样重新编号，从而使得新的编号连续。更新根节点编号、结点数量并对每条有向边$(u_i,v_i,w_i)$做更新$w_i=w_i-w[v_i];u_i=id[ui];v_i=id[v_i]$然后回到步骤1。

   朱-刘算法核心思想就是缩圈（对结点重新编号）并修改边权，有些版本的实现有一个DFS/BFS预处理：判断根结点是否可以到达其他所有结点。这里给出的实现版本不做预处理，而是在反复缩圈的过程中检查是否有孤立点（有孤立点说明根结点无法到达部分结点）。

不固定根的最小树形图求法

   新加一个点作为根，和原图每个点连一条边权相同的有向边，这个权值大于原图所有边权的最大值，求出固定根最小树形图，也就求出了原图不固定根的最小树形图。

AC 代码

#include <iostream>
#include <cstring>
using namespace std;

#define M 10010
#define N 63
int g[N][M], s[N], q[N], f[N], w[N], id[N], vis[N], m, n, c;
struct edge {int u, v, b, c;} e0[M], e[M];

bool check(int x) {
    memcpy(e, e0, sizeof(e));
    for (int i=0; i<n; ++i) f[i] = 0;
    int head = 0, tail = 1; f[q[0] = 0] = 1;
    while (head < tail) {
        int u = q[head++];
        for (int i=0; i<s[u]; ++i) {
            const edge &eg = e[g[u][i]];
            if (eg.b < x) continue;
            if (!f[eg.v]) {
                q[tail] = eg.v; f[eg.v] = 1;
                if (++tail == n) break;
            }
        }
        if (tail == n) break;
    }
    if (tail < n) return false;
    int ans = 0, r = 0, k = n;
    while (true) {
        for (int i=0; i<k; ++i) f[i] = i;
        for (int i=0; i<m; ++i) if (e[i].b >= x && e[i].u != e[i].v) {
            int u = e[i].u, v = e[i].v;
            if (f[v] == v || e[i].c < w[v]) f[v] = u, w[v] = e[i].c;
        }
        int t = w[r] = 0;
        for (int i=0; i<k; ++i) id[i] = vis[i] = -1;
        for (int i=0, v; i<k; ++i) {
            ans += w[i];
            for (v = i; vis[v] != i && id[v] < 0 && v != r; v = f[v]) vis[v] = i;
            if (id[v] < 0 && v != r) {
                for (int u = f[v]; u != v; u = f[u]) id[u] = t;
                id[v] = t++;
            }
        }
        if (t == 0) break;
        for (int i=0; i<k; ++i) if (id[i] < 0) id[i] = t++;
        for (int i=0; i<m; ++i) if (e[i].b >= x) {
            int u = e[i].u, v = e[i].v;
            e[i].u = id[u]; e[i].v = id[v]; e[i].c -= w[v];
        }
        k = t; r = id[r];
    }
    return ans <= c;
}

void solve() {
    cin >> n >> m >> c;
    for (int i=0; i<n; ++i) s[i] = 0;
    int l = 2000000, r = 0;
    for (int i=0; i<m; ++i) {
        cin >> e0[i].u >> e0[i].v >> e0[i].b >> e0[i].c;
        l = min(l, e0[i].b); r = max(r, e0[i].b); g[e0[i].u][s[e0[i].u]++] = i;
    }
    if (!check(l)) {
        cout << "streaming not possible." << endl;
        return;
    }
    while (l < r) {
        int m = (l+r+1)>>1;
        check(m) ? l = m : r = m-1;
    }
    cout << l << " kbps" << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}