Problem Solving►UVa

UVa 10330 - Power Transmission

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

點上的權重，就將它分成 in 和 out 的點，之間的邊的權重即是點的。(可參考 UVa 11506)
對於起點和目的地，這裡用 0: B, 1: D。

而發電廠和最後城市相連的邊就設大一點(無限大)，接著做 Dinic Algo. 找最大流即可。

Code

UVa 10330
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
//Zerojudge 上要使用 scanf
#include <cstdio>
#include <cstring>
#include <queue>
#define N 205
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define IN(x) ((x) << 1)
#define OUT(x) (IN(x) + 1)
using namespace std;

int n;
int adj[N][N];
int d[N];
bool visited[N];
inline int read()
{
    int n = 0;
    char ch;
    while ((ch = getchar()) >= '0' && ch <= '9')
        n = n * 10 + ch - '0';

    return n;
}
void BFS()
{
    memset(d, 0, sizeof d);
    queue<int> Q;
    Q.push(0);
    d[0] = 1; //B
    while (!Q.empty())
    {
        int now = Q.front();
        Q.pop();
        for (int i = 1; i <= OUT(n); ++i)
        {
            if (adj[now][i] > 0 && !d[i])
            {
                d[i] = d[now] + 1;

                if (i == 1) //D
                    return;

                Q.push(i);
            }
        }
    }
}
int DFS(int from, int df)
{
    if (from == 1)
        return df;

    for (int i = 1; i <= OUT(n); ++i)
    {
        if (adj[from][i] > 0 && !visited[i] && d[from] + 1 == d[i])
        {
            int f = DFS(i, MIN(df, adj[from][i]));
            visited[i] = true;
            if (f != 0)
            {
                adj[from][i] -= f;
                adj[i][from] += f;
                return f;
            }
        }
    }

    return 0;
}
int main()
{
    //freopen("test.out", "w", stdout);
    int m;
    while (scanf("%d", &n) != EOF)
    {
        getchar();
        //0: B, 1: D
        int u, v, c;
        for (int i = 1; i <= n; ++i)
        {
            //scanf("%d", &c);
            c = read();
            adj[OUT(i)][IN(i)] = adj[IN(i)][OUT(i)] = c;
        }

        scanf("%d ", &m);
        for (int i = 0; i < m; ++i)
        {
            u = read();
            v = read();
            c = read();
            //scanf("%d%d%d", &u, &v, &c);
            adj[OUT(u)][IN(v)] += c;
        }

        int B, D;
        scanf("%d%d ", &B, &D);
        for (int i = 0; i < B; ++i)
        {
            //scanf("%d", &u);
            u = read();
            adj[0][IN(u)] = 1e9;
        }
        for (int i = 0; i < D; ++i)
        {
            //scanf("%d", &u);
            u = read();
            adj[OUT(u)][1] = 1e9;
        }

        //Dinic Algo.
        int flow = 0;
        while (true)
        {
            BFS();
            if (!d[1])
                break;
            int f = 0;
            while (true)
            {
                memset(visited, false, sizeof visited);
                if ((f = DFS(0, 1e9)) != 0)
                    flow += f;
                else
                    break;
            }
        }

        printf("%d\n", flow);

        //init
        for (int i = 0; i <= OUT(n); ++i)
            memset(adj[i], 0, sizeof adj[i]);
    }

    return 0;
}