취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 20135번 문제인 연세 마스크 공장이다.
문제는 아래 링크를 확인하자.

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

마스크가 지하에서 공급되는 것을 source와의 연결, 마스크를 지하로 공급하는 것을 sink와의 연결로 생각하는 유량 그래프를 그리고, source와 연결된 모든 간선과 sink와 연결된 모든 간선의 유량을 꽉 채울 수 있는지를 확인하는 것으로 문제를 해결하자.

이런 상황 하에서 u->v 간선의 유량이 s 이상 e 이하여야한다는 조건은 u에서 sink로 s, source에서 v로 s, u에서 v로 (e-s)의 가중치를 가진 그래프에서 유량을 흘린 뒤 , source와 연결된 모든 간선과 sink와 연결된 모든 간선의 유량을 꽉 채울 수 있는지를 확인하는 것과 같다.

위 내용의 자세한 설명은 circulation 등을 검색하면 쉽게 찾을 수 있을 것이다.

주어지는 가중치가 int범위를 넘어설 수 있으니 자료형에 유의하자.

아래는 제출한 소스코드이다.

#define NODE 202
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;

int N, M;
int source, sink;
ll edge[NODE][NODE];
vector<int> G[NODE];
int level[NODE];

bool dinic_bfs() { // 현 단계의 level graph 생성; 리턴값: 성공여부
	memset(level, 0, sizeof(level));
	level[source] = 1;
	queue<int> que;
	que.push(source);
	while (!que.empty()) {
		int& cur = que.front();
		for (auto& node : G[cur]) {
			if (edge[cur][node] && level[node] == 0) {
				level[node] = level[cur] + 1;
				que.push(node);
			}
		}
		que.pop();
	}

	return level[sink];
}

int turn[NODE];

ll dinic_dfs(int cur, ll flow) { // flow값 오버플로우 주의
	if (cur == sink) return flow;
	int cursize = G[cur].size();
	for (int& i = turn[cur]; i < cursize; i++) {
		int& node = G[cur][i];
		if (edge[cur][node] && level[node] == level[cur] + 1) {
			ll tmp = dinic_dfs(node, min(edge[cur][node], flow));
			if (tmp) {
				edge[cur][node] -= tmp;
				edge[node][cur] += tmp;
				return tmp;
			}
		}
	}

	return 0;
}

ll dinic() { // 실제 maximum flow 계산
	ll ret = 0;
	while (dinic_bfs()) {
		memset(turn, 0, sizeof(turn));
		ll f;
		while (f = dinic_dfs(source, 1000000000000000007LL)) ret += f;
	}

	return ret;
}

struct qedge {
	int u, v; ll c;
	qedge() {};
	qedge(int u, int v, ll c) {
		this->u = u, this->v = v, this->c = c;
	}
};

qedge qedges[1000];

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

	cin >> N >> M;
	source = 0, sink = N + 1;

	ll outflow = 0, inflow = 0;
	for (int i = 1; i <= N; i++) {
		ll x; cin >> x;
		if (x >= 0) edge[source][i] = x, outflow += x, G[source].emplace_back(i), G[i].emplace_back(source);
		else edge[i][sink] = -x, inflow -= x, G[i].emplace_back(sink), G[sink].emplace_back(i);
	}
	for (int m = 0; m < M; m++) {
		int u, v; ll s, e; cin >> u >> v >> s >> e;
		qedges[m] = qedge(u, v, s);
		edge[u][sink] += s;
		G[u].emplace_back(sink);
		G[sink].emplace_back(u);
		edge[source][v] += s;
		G[source].emplace_back(v);
		G[v].emplace_back(source);
		edge[u][v] = e - s;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
		inflow += s, outflow += s;
	}

	if (outflow != inflow || dinic() != outflow) cout << -1;
	else {
		cout << 1 << '\n';
		for (int m = 0; m < M; m++) {
			int u = qedges[m].u, v = qedges[m].v; ll c = qedges[m].c;
			cout << edge[v][u] + c << '\n';
		}
	}
}