UVa

UVa10594 Data Flow

連結：https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1535
題意：給定一張無向圖，每條邊的容量為 $K$，但各自有不同的成本，試問從 $1$ 到 $n$ 傳 $D$ 單位資料最小成本為多少

解法：這題是題最小花費最大流的題目，最主要就是會建模
相關連結：http://programming-study-notes.blogspot.com/2014/05/uva-10594-data-flow.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
using LL = long long;
const int MXV = 105;
const LL INF = 1e9;
#define IOS                                                                    \
    cin.tie(nullptr);                                                          \
    cout.tie(nullptr);                                                         \
    ios_base::sync_with_stdio(false);

template <typename T> struct MCMF
{
    int n, pre[MXV];
    T dis[MXV], cap[MXV][MXV], flow[MXV][MXV], cost[MXV][MXV];
    vector<int> edges[MXV];
    bitset<MXV> inque;
    queue<int> q;
    void init(int _n)
    {
        n = _n;
        memset(cap, 0, sizeof(cap));
        memset(flow, 0, sizeof(flow));
        memset(cost, 0, sizeof(cost));
        for (int i = 0; i <= n; ++i)
        {
            edges[i].clear();
        }
    }
    void addEdge(int u, int v, T c)
    {
        edges[u].push_back(v);
        edges[v].push_back(u);
        cost[u][v] = cost[v][u] = c;
    }
    void setCap(T k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j : edges[i])
            {
                cap[i][j] = k;
            }
        }
    }
    bool spfa(int s, int t)
    {
        fill(begin(dis), end(dis), INF);
        inque.reset();
        while (!q.empty())
        {
            q.pop();
        }
        dis[s] = 0;
        q.push(s);
        inque[s] = true;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            inque[u] = false;
            for (int v : edges[u])
            {
                if (flow[v][u] > 0 && dis[v] > dis[u] + (-cost[v][u]))
                {
                    dis[v] = dis[u] + (-cost[v][u]);
                    pre[v] = u;
                    // cout << u << ' ' << v << ' ' << dis[v] << '\n';
                    if (!inque[v])
                    {
                        q.push(v);
                        inque[v] = true;
                    }
                }
                else if (cap[u][v] > flow[u][v] && dis[v] > dis[u] + cost[u][v])
                {
                    dis[v] = dis[u] + cost[u][v];
                    pre[v] = u;
                    // cout << u << ' ' << v << ' ' << dis[v] << ' ' << cost[u][v] << '\n';
                    if (!inque[v])
                    {
                        q.push(v);
                        inque[v] = true;
                    }
                }
            }
        }
        return dis[t] != INF;
    }
    void update(int s, int t, T bottleneck)
    {
        for (int u = t; u != s; u = pre[u])
        {
            flow[pre[u]][u] += bottleneck;
            flow[u][pre[u]] -= bottleneck;
        }
    }
    T findbottleneck(int s, int t)
    {
        T bottleneck = INF;
        for (int u = t; u != s; u = pre[u])
        {
            bottleneck = min(bottleneck, cap[pre[u]][u] - flow[pre[u]][u]);
        }
        return bottleneck;
    }
    void sol(int s, int t, T D)
    {
        T mnCost = 0, mxFlow = 0;
        while (spfa(s, t))
        {
            T bottleneck = findbottleneck(s, t);
            update(s, t, bottleneck);
            mxFlow += bottleneck;
            mnCost += bottleneck * dis[t];
        }
        if (mxFlow != D)
        {
            cout << "Impossible.\n";
        }
        else
        {
            cout << mnCost << '\n';
        }
    }
};

int main()
{
    IOS;
    MCMF<LL> mcmf;
    int n, m;
    LL d, k;
    while (cin >> n >> m)
    {
        mcmf.init(n);
        LL z;
        for (int i = 0, x, y; i < m; ++i)
        {
            cin >> x >> y >> z;
            mcmf.addEdge(x, y, z);
        }
        cin >> d >> k;
        mcmf.setCap(k);
        mcmf.edges[0].push_back(1);
        mcmf.cap[0][1] = d;
        mcmf.sol(0, n, d);
    }
}

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts