반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 네트워크 플로우 :: http://www.crocus.co.kr/741

2. 최대 유량



완전 중요한 간선을 알기 위해서는 다음과 같은 과정을 거치면 된다.


1. 입력으로 주어지는 from, to 값을 다른 공간에 저장해둔다.

 

2. 최대 유량을 구한다.(최대 유량이 몇인지는 구하지 않아도 되고, Maximum flow 알고리즘(폴커슨, 애드먼드, 디닉 등등)을 이용한다.)


3. 1에서 저장해둔 두 값을 S, T로 생각하고 그 정점 -> 정점으로 유량이 흐르는지 검사해본다면 이것이 완전 중요한 간선인지 아닌지 알 수 있다.(1에서 저장한 값 모두를 조사하면 몇개의 간선이 완전 중요한 간선인지 나타난다.)


왜냐면 그것이 완전 중요한 간선이라면 그 간선을 만들고 있는 정점을 A, B라 하고, 이때 최대 유량을 구했을 때 A->B에는 최대 유량이 흐르고 있을 것이고 만약, 용량이 1 준다면 최대 유량도 1 줄기 때문이다.


만약 완전 중요한 간선이 아니었다면, A->B의 용량을 1 줄여도 최대 유량보다 크거나 같거나, 아니면 다른 간선을 통해 그 부분을 메워줄 수 있기 때문이다. 







소스 코드 : 


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
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <memory.h>
 
#define INF 987654321
 
using namespace std;
 
typedef pair<intint> pii;
 
vector<vector<int>> adj, c, f;
 
int main()
{
    int tc;
    scanf("%d"&tc);
 
    while (tc--)
    {
        int n, m;
        scanf("%d %d"&n, &m);
 
        f = c = vector<vector<int>>(n + 1, vector<int>(n + 10));
        adj = vector<vector<int>>(n + 1);
 
        vector<pii> vc;
 
        for (int i = 0; i < m; i++)
        {
            int from, to, val;
            scanf("%d %d %d"&from, &to, &val);
 
            adj[from].push_back(to);
            adj[to].push_back(from); // 역방향 간선
 
            c[from][to] += val;
 
            vc.push_back({ from,to });
        }
 
        // 에드몬드 카프 알고리즘
        int totalFlow = 0, S = 1, T = n;
        while (1)
        {
            vector<int> prev(n + 1-1);
 
            queue<int> q;
            q.push(S);
 
            while (!q.empty() && prev[T] == -1)
            {
                int cur = q.front();
                q.pop();
 
                for (int i = 0; i < adj[cur].size(); i++)
                {
                    int next = adj[cur][i];
 
                    if (prev[next] != -1)
                        continue;
 
                    if (c[cur][next] - f[cur][next] > 0)
                    {
                        q.push(next);
                        prev[next] = cur;
                    }
                }
            }
 
            if (prev[T] == -1)
                break;
 
            int flow = INF;
 
            for (int i = T; i != S; i = prev[i])
                flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);
 
            for (int i = T; i != S; i = prev[i])
            {
                f[prev[i]][i] += flow;
                f[i][prev[i]] -= flow;
            }
            totalFlow += flow;
        }
 
        // 완전 중요한 간선인지 확인
        int ans = 0;
        for (int i = 0; i < vc.size(); i++)
        {
            int S = vc[i].first;
            int T = vc[i].second;
 
            vector<int> prev(n + 1-1);
 
            queue<int> q;
            q.push(S);
 
            while (!q.empty() && prev[T] == -1)
            {
                int cur = q.front();
                q.pop();
 
                for (int i = 0; i < adj[cur].size(); i++)
                {
                    int next = adj[cur][i];
                    if (prev[next] != -1)
                        continue;
 
                    if (c[cur][next] - f[cur][next] > 0)
                    {
                        prev[next] = cur;
                        q.push(next);
                    }
                }
            }
 
            if (prev[T] == -1)
                ans++;
        }
 
        printf("%d\n", ans);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1014번] 컨닝  (2) 2017.04.24
[1431번] 시리얼 번호  (0) 2017.04.24
[1074번] Z  (0) 2017.04.22
[1780번] 종이의 개수  (0) 2017.04.22
[9291번] 스도쿠 채점  (2) 2017.04.22