[UVA 11865]Stream My Contest[最小ツリー図][二分答案]

タイトルリンク:[UVA 11865]Stream My Contest[最小ツリー図][二分答案]テーマ分析:サーバー(ノード0)からすべての大学のネットワークを構築し、実行可能なネットワークの中で、最小帯域幅が最大のネットワークに対応する帯域幅はいくらですか?テーマには2つの制限があります.

大学間にはもともとネットワークがないので、ネットワークを構築する必要があり、一定の費用がかかり、最大予算はC元で、一方的です.

大学間のネットワークには帯域幅があり、生成されたネットワークでは、トラフィックが最小帯域幅を超えてはいけません.そうしないと、指定されたユーザーに送信できません.

问题解决の考え方:サーバーはすべてのノードに届いて、とても最小の木の形の図に合います==.しかし、本題には複数の制限条件があり、すべての生成ツリーの中で、最小エッジ権の最大値はいくらですか?この最小エッジ権を列挙して、この最小エッジ権より大きい最小ツリー図が存在するかどうかを列挙し、絶えず二分すればよい.个人感受:题目の第2の制限条件は半日见て、英语は急いで==を捕まえます.また、2つの制限条件の下の言葉もおかしいと思います.帯域幅を共有するなどのOrzの具体的なコードは以下の通りです.

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;

const int INF = 0x7f7f7f7f;
const int MAXN = 1e4 + 111;

struct Edge{
    int u, v, band, cost;
}edge[MAXN * 2];

int n, m, C, pre[100], vis[100], newid[100], in[100];

void add_edge(int cnt, int u, int v, int band, int cost)
{
    edge[cnt + m].u = edge[cnt].u = u;
    edge[cnt + m].v = edge[cnt].v = v;
    edge[cnt + m].band = edge[cnt].band = band;
    edge[cnt + m].cost = edge[cnt].cost = cost;
}

bool zhuLiu(int rt, int V, int miband)
{
    ll ret = 0;
    while (1)
    {
        for (int i = 0; i < V; ++i) in[i] = INF;
        for (int i = 0; i < m; ++i)
        {
            int u = edge[i].u, v = edge[i].v;
            if (u != v && edge[i].band >= miband && in[v] > edge[i].cost)
            {
                in[v] = edge[i].cost;
                pre[v] = u;
            }
        }
        for (int i = 0; i < V; ++i)
        {
            if (i != rt && in[i] == INF) return 0;
        }

        int cnt = 0;
        memset(newid, -1, sizeof newid);
        memset(vis, -1, sizeof vis);
        in[rt] = 0;
        for (int i = 0; i < V; ++i)
        {
            ret += in[i];
            int v = i;
            while (vis[v] != i && newid[v] == -1 && v != rt)
            {
                vis[v] = i;
                v = pre[v];
            }
            if (v != rt && newid[v] == -1)
            {
                for (int u = pre[v]; u != v; u = pre[u]) newid[u] = cnt;
                newid[v] = cnt++;
            }
        }

        if (cnt == 0) break;
        for (int i = 0; i < V; ++i)
            if (newid[i] == -1) newid[i] = cnt++;

        for (int i = 0; i < m; ++i)
        {
            int u = edge[i].u, v = edge[i].v;
            edge[i].u = newid[u];
            edge[i].v = newid[v];
            if (newid[u] != newid[v]) edge[i].cost -= in[v];
        }
        V = cnt;
        rt = newid[rt];
    }
    return (ret <= C);
}

int main()
{
    int t, a, b, c, d; scanf("%d", &t);
    while (t --)
    {
        scanf("%d%d%d", &n, &m, &C);
        int mi = INF, mx = 0;
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            add_edge(i, a, b, c, d);
            mi = min(mi, c);
            mx = max(mx, c);
        }

        if (!zhuLiu(0, n, mi)) printf("streaming not possible.
"); //           
        else
        {
            int l = mi, r = mx;
            while (l <= r)
            {
                int mid = (l + r) >> 1;
                for (int i = 0; i < m; ++i) //     ，             
                    edge[i] = edge[i + m];
                if (zhuLiu(0, n, mid)) l = mid + 1;
                else r = mid - 1;
            }
            printf("%d kbps
", r);
        }
    }
    return 0;
}