acmicpc.net 6086(네트워크 플로우), 2188(네트워크 플로우)

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

주의할점 : a에서 b까지 가는 경로가 여러개 있을수 있어 대역폭을 더해줘야 함.

#include<cstdio>
#include<iostream>
#include<vector>
#include <queue>
using namespace std;

const int MAX_V = 500;
int V = 52;
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V];
vector<int> adj[MAX_V];

int networkFlow(int source, int sink) {
	//memset(flow, 0, sizeof(flow));
	for(int i=0;i<MAX_V;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() && parent[sink]==-1) {
			int here = q.front(); q.pop();
			//for(int there = 0; there < V; ++there)
			for(auto &there : adj[here])
				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;
	//cout<<'Z'-0;
	cin >> E;// >> E; //V는 정점의 갯수, E는 대역폭의 갯수
	//memset(capacity, 0, sizeof(capacity)); 
	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) {
		char a, b;
		int c;
		cin >> a >> b >> c; //a에서 b까지가는데 c의 대역폭이 있다.
		capacity[a-65][b-65] += c;
		adj[a-65].push_back(b-65);
		adj[b-65].push_back(a-65);
		
	}
	cout << networkFlow(0, 'Z'-65) << endl;
	/*for(int i = 0; i < V; ++i)
	for(int j = 0; j < V; ++j)
	if(flow[i][j] > 0)
	cout << i << " => " << j << ": " << flow[i][j] << endl;*/
}

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

축사 배정 문제. 솔직히 그래프 모델링을 어떻게 해야될지 몰랐다. http://kks227.blog.me/220796029558 글에서 아래 그림을 보고 풀수 있었다.

#include<cstdio>
#include<iostream>
#include<vector>
#include <queue>
using namespace std;

const int MAX_V = 999;

int V;
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V];

int networkFlow(int source, int sink) {
	//memset(flow, 0, sizeof(flow));
	for(int i=0;i<MAX_V;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) //여기 범위를 V까지가 아니라 내가 만든 MAX_V로 변경해줘야됨.
				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; //V는 정점의 갯수, E는 대역폭의 갯수
	//memset(capacity, 0, sizeof(capacity)); 
	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 < V; ++i) {
		int n;
		cin>>n;
		//cout<<0<<" -> "<<i+1<<endl;
		for(int j=0;j<n;j++)
		{
			int a;//, b, c;
			cin >> a;
			capacity[0][i+1] = 1; //위의 그림에서 S가 0 즉 시작점이고 i+1, 소로 갈수있다.
			capacity[i+1][200 + a] = 1; //소 i+1에서 축사 a위치로 가고싶다. (축사의 시작점은 201부터 시작한다고 가정한다.)
			capacity[200 + a][500] = 1; //축사에서 끝점 500까지 가는게 가능하다.
			//cout<<"  -> "<<200+a<<" -> "<<500<<"\n";
		}
		//cout<<endl;
	}
	/*for(int i=0;i<V;i++)
		capacity[500][i+1] = 1;
	for(int i=0;i<V;i++)
		capacity[i+201][600] = 1;*/

	cout << networkFlow(0, 500) << endl;
	/*for(int i = 0; i < V; ++i)
		for(int j = 0; j < V; ++j)
			if(flow[i][j] > 0)
				cout << i << " => " << j << ": " << flow[i][j] << endl;*/
}