[5651번] 완전 중요한 간선

문제 출처 :

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 줄여도 최대 유량보다 크거나 같거나, 아니면 다른 간선을 통해 그 부분을 메워줄 수 있기 때문이다. 

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <memory.h>
 
#define INF 987654321
 
using namespace std;
 
typedef pair<int, int> 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 + 1, 0));
        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 >>