acmicpc.net 2252(위상 정렬), 1298(네트워크 플로우)

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

옛날의 위상정렬 코드를 가져와서 변경했다. http://qkqhxla1.tistory.com/640

#include <iostream>
#include <queue>
using namespace std;
  
int main()
{
    int n,m,a,b;
	vector<int> adj[33000];
    int indegree[100001]={0,};
    cin>>n>>m; 
    for(int i=0;i<m;i++) 
    {
        int p,temp[1001]={0,};
		cin>>a>>b;
		indegree[b]++;
		adj[a].push_back(b);
    }
 
    queue<int> q;
    for(int i=1;i<n+1;i++) 
        if(indegree[i]==0)
            q.push(i);
 
    int answer[100001]={0,},c=0;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        answer[c++] = u;

        for(int i=0;i<adj[u].size();i++)
        {
            indegree[adj[u][i]]--;
            if(indegree[adj[u][i]]==0)
                q.push(adj[u][i]);
        }
    }
 
    int l = 0; 
    for(int i=0;answer[i]!=0;i++)
        l++;
    if(l==n)
        for(int i=0;answer[i]!=0;i++)
            cout<<answer[i]<<" ";
    else
        cout<<0<<endl;
    return 0;
}

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

앞의 축사 문제(2188)랑 거의 비슷하다.

#include<cstdio>
#include<iostream>
#include<vector>
#include <queue>
using namespace std;
 
const int MAX_X = 600;
const int MAX_V = 600;
 
int V;
int capacity[MAX_X][MAX_V], flow[MAX_X][MAX_V];
 
int networkFlow(int source, int sink) {
    //memset(flow, 0, sizeof(flow));
    for(int i=0;i<MAX_X;i++)
        for(int j=0;j<MAX_V;j++)
            flow[i][j] = 0;
    int totalFlow = 0;
 
    while(true) {
        vector<int> parent(MAX_V, -1);
        queue<int> q;
        parent[source] = source;
        q.push(source);
        while(!q.empty()) {
            int here = q.front(); q.pop();
            for(int there = 0; there < MAX_V; ++there) 
                if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1) {
                    q.push(there);
                    parent[there] = here;
                }
        }
        if(parent[sink] == -1) break;
        int amount = 987654321;
        for(int p = sink; p != source; p = parent[p])
            amount = min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
        for(int p = sink; p != source; p = parent[p]) {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        totalFlow += amount;
    }
 
    return totalFlow;
}
 
int main() {
    int E;
    cin >> V >> E;
    for(int i=0;i<MAX_V;i++)
        for(int j=0;j<MAX_V;j++)
            capacity[i][j] = 0;
    for(int i = 0; i < E; ++i) {
            int a, b;//, c;
            cin >> a >> b;
            capacity[0][a] = 1; 
            capacity[a][200 + b] = 1; 
            capacity[200 + b][500] = 1; 
    }
    cout << networkFlow(0, 500) << endl;
}