Algorithm/BOJ

최대 유량 - 6086

jhg0406 2020. 2. 25. 00:21
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
//6086 - 최대 유량
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
#define MAX_V 52
#define INF 200000000
 
int M;
vector<int> adj[MAX_V];
int level[MAX_V], work[MAX_V];
int capa[MAX_V][MAX_V];
int flow[MAX_V][MAX_V];
 
int ctoi(char c)
{
    if(c >= 'a')
        return c-'a'+26;
    return c-'A';
}
 
void init()
{
    cin >> M;
    char c1, c2;
    int cost;
    for(int i = 0; i<M; ++i)
    {
        cin >> c1 >> c2 >> cost;
        c1 = ctoi(c1);
        c2 = ctoi(c2);
        
        adj[c1].push_back(c2);
        adj[c2].push_back(c1);
        capa[c1][c2] += cost;
        capa[c2][c1] += cost;
    }
}
 
bool bfs()
{
    fill(level, level+MAX_V, -1);
    level[0] = 0;
    queue<int> Q;
    Q.push(0);
 
    while(!Q.empty())
    {
        int curr = Q.front();
        Q.pop();
        for(int next : adj[curr])
            if(level[next] == -1 && capa[curr][next] - flow[curr][next] > 0)
            {
                level[next] = level[curr]+1;
                Q.push(next);
            }
    }
    return level[25] != -1;
}
 
int dfs(int source, int dest, int f)
{
    if(source == dest) return f;
 
    for(int& i = work[source]; i < adj[source].size(); i++)
    {
        int next = adj[source][i];
        if(level[next] == level[source]+1 && capa[source][next] - flow[source][next] > 0)
        {
            int df = dfs(next, dest, min(f, capa[source][next] - flow[source][next]));
            if(df != 0)
            {
                flow[source][next] += df;
                flow[next][source] -= df;
                return df;
            }
        }
    }
    return 0;
}
 
int Dinic()
{
    int ret = 0;
 
    while(bfs())
    {
        fill(work, work+MAX_V, 0);
        while(1)
        {
            int f = dfs(0, 25, INF);
            if(f == 0)
                break;
            ret += f;
        }
    }
    return ret;
}
 
int main()
{
    init();
    cout << Dinic();
}
 cs

 

 

 

 

 

 

https://www.acmicpc.net/problem/6086

 

6086번: 최대 유량

문제 농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다. 두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한개의 용량 3짜리 파이프가 된다. +---5---+

www.acmicpc.net

 

 

 

 

 

 

최대 유량

문제 제목 그대로 최대 유량 문제입니다! 양방향 간선인것에 주의해야 합니다.

Dinic's algorithm을 사용해 해결했습니다.