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를 이용해서 돌도록 하니까 해결이 되었다..

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

이 문제에서는 도시를 한번만 방문하면서

최대 유량을 구해야한다.

도시를 한번만 방문해야하는 조건을 구현하기 위해

정점을 분할해주어야한다.

정점을 분할해주고 정점과 정점' 를 연결해주는 간선의 Capacity를 1로 두면

해당 정점을 최대 한 번만 방문하도록 할 수 있다.

#include <bits/stdc++.h>
using namespace std;

const int MAX = 810;
int n, p, res;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];

void maxFlow(int start, int end) {
    while (1) {
        fill(d, d + MAX, -1);

        queue<int> Q;
        Q.push(start);
        d[start] = 0;

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

            for (int i = 0; i < adj[x].size(); i++) {
                int nx = adj[x][i];

                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    Q.push(nx);
                    d[nx] = x;

                    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;
        }

        res += flow;
    }
}



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

    cin >> n >> p;

    for (int i = 1; i <= n; i++) {
		int x = 2 * i;
        int x_ = 2 * i - 1;

        c[x][x_] = 1;
        adj[x_].push_back(x);
        adj[x].push_back(x_);
    }

    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        int u = a * 2;
		int u_ = a * 2 - 1;

		int v = b * 2;
        int v_ = b * 2 - 1;

        c[u_][v] = 1;
        c[v_][u] = 1;
        adj[u_].push_back(v);
        adj[v].push_back(u_);

        adj[v_].push_back(u);
        adj[u].push_back(v_);
    }

    maxFlow(1, 4);

    cout << res << '\n';
    return 0;
}

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

#include <bits/stdc++.h>
#include <unordered_set>

#define MAX 800
#define INF 1e9;

using namespace std;

int n, res;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];

void maxFlow(int start, int end) {
    while (1) {
        fill(d, d + MAX, -1);
        queue<int> Q;

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

            for (int i = 0; i < adj[x].size(); i++) {
                int nx = adj[x][i];

                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    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;
        }

        res += flow;
    }
}

int CtoI(char c) {
    if (c <= 'Z') {
		return c - 'A';
    }
    else {
        return (c - 'a') + 26;
    }
}

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        char a, b;
        int q;
        cin >> a >> b >> q;

        int u = CtoI(a);
        int v = CtoI(b);
        c[u][v] += q;
        c[v][u] += q;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    maxFlow(0, 25);

    cout << res << '\n';

    return 0;
}