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

1.문제접근 및 알고리즘

최대 유량이 흐르는 상태를 구현한 뒤

간선마다 검사를 해주면서 더이상 유량이 흐를수 없는 상태라면

즉 해당 간선의 용량과 흐르는 유량이 일치하는 상태라면

그 간선은 완전 중요한 간선이 된다.

2. 주의할점

1.

 a 에서 b 로 가는 간선이 여러개 있을 수 있으니

용량을 계속 더해주어야한다

2.

계속 푸는데 시간초과가 나서 for문을 auto로 바꿔주니 시간초과가 해결되었다.

앞으로는 웬만하면 auto를 사용해주어야겠다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

const int MAX = 333;

int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];
vector<pair<int, int> > edge;
int n, m;

void maxFlow(int start, int end) {
    while (1) {
        memset(d, -1, sizeof(d));
        queue<int> Q;
        Q.push(start);

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front();
            Q.pop();

            for(auto nx : adj[x]){
                if (c[x][nx] - f[x][nx] > 0 && d[nx] == -1) {
                    d[nx] = x;
                    Q.push(nx);
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) break;
        int flow = INT_MAX;

        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }

        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }
    }


}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int k;
    cin >> k;
    for (int T = 0; T < k; T++) {
        memset(c, 0, sizeof(c));
        memset(f, 0, sizeof(f));
        for (int i = 0; i < MAX; i++) adj[i].clear();
        edge.clear();
        cin >> n >> m;

        for (int i = 0; i < m; i++) {
            int a, b, d;
            cin >> a >> b >> d;
            

            c[a][b] += d;
            adj[a].push_back(b);
            adj[b].push_back(a);
            edge.push_back({ a,b });
        }


        maxFlow(1, n);

        int ans = 0;

        for (int i = 0; i < edge.size(); i++) {
            int S = edge[i].first;
            int T = edge[i].second;
            int prev[MAX];
            memset(prev, -1, sizeof(prev));

            queue<int> Q;
            Q.push(S);

            while (!Q.empty()) {
                int x = Q.front();
                Q.pop();

                for (auto nx : adj[x]) {
                    if (prev[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                        prev[nx] = x;
                        Q.push(nx);
                    }
                }
            }

            if (prev[T] == -1) ans++;
        }

        cout << ans << '\n';
    }


    return 0;
}

저 많은 시간초과들은

for문을 auto를 이용해서 돌도록 하니까 해결이 되었다..