UVa

uva10806 Dijkstra, Dijkstra

題目連結：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1747
題意：給你一張無向圖，邊上有花費權重，問有沒有辦法從點 $1$ 出發到點 $n$，然後再從點 $n$ 回到點 $1$ 的兩條不重複邊的路徑，如果有，請輸出最小成本

解法：最小花費最大流，走過去再走回來，相當於把每條邊流量設 $1$，問有沒有最大流是否 $\geq 2$。

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
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
#define IOS                                                                    \
    cin.tie(nullptr);                                                          \
    cout.tie(nullptr);                                                         \
    ios_base::sync_with_stdio(false);
const int MXV = 205;
const int INF = 1e9;

template <typename T> struct MCMF
{
    int n, dis[MXV], pre[MXV];
    int cap[MXV][MXV], flow[MXV][MXV];
    struct Edge
    {
        int v;
        T rf;
        int re;
    };
    vector<Edge> edges[MXV];
    bitset<MXV> inque, used[MXV];
    queue<int> q;
    void init(int _n)
    {
        n = _n;
        memset(cap, 0, sizeof(cap));
        memset(flow, 0, sizeof(flow));
        for (int i = 0; i <= n; ++i)
        {
            edges[i].clear();
            used[i].reset();
        }
    }
    void addEdge(int u, int v, T rf)
    {
        cap[u][v] = cap[v][u] = rf;
        edges[u].push_back({v, rf, (int)edges[v].size()});
        edges[v].push_back({u, rf, (int)edges[u].size() - 1});
    }
    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);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            inque[u] = false;
            for (Edge &e : edges[u])
            {
                int v = e.v;
                if (flow[v][u] > 0 && dis[v] > dis[u] + (-e.rf))
                {
                    dis[v] = dis[u] + (-e.rf);
                    pre[v] = u;
                    if (!inque[v])
                    {
                        q.push(v);
                        inque[v] = true;
                    }
                }
                else if (!used[u][v] && cap[u][v] > flow[u][v] &&
                         dis[v] > dis[u] + e.rf)
                {
                    dis[v] = dis[u] + e.rf;
                    pre[v] = u;
                    if (!inque[v])
                    {
                        q.push(v);
                        inque[v] = true;
                    }
                }
            }
        }
        return dis[t] != INF;
    }
    void update(int s, int t, int bottleneck)
    {
        for (int u = t; u != s; u = pre[u])
        {
            flow[pre[u]][u] += bottleneck;
            flow[u][pre[u]] -= bottleneck;
            used[pre[u]][u] = used[u][pre[u]] = true;
        }
    }
    void sol(int s, int t)
    {
        int mnCost = 0, mxFlow = 0;
        while (spfa(s, t))
        {
            update(s, t, 1);
            ++mxFlow;
            mnCost += dis[t];
            if (mxFlow >= 2)
            {
                break;
            }
        }
        if (mxFlow < 2)
        {
            cout << "Back to jail\n";
        }
        else
        {
            cout << mnCost << '\n';
        }
    }
};

int main()
{
    // IOS;
    int n, m;
    MCMF<int> mcmf;
    while (cin >> n, n)
    {
        cin >> m;
        mcmf.init(n);
        for(int i = 0, f, t, w; i != m; ++i)
        {
            cin >> f >> t >> w;
            mcmf.addEdge(f, t, w);
        }
        mcmf.sol(n, 1);
    }
}

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

Recommended Posts