[BOJ 10319] 좀비 아포칼립스

문제 출처 : https://www.acmicpc.net/problem/10319

10319번: 좀비 아포칼립스

 

풀이 :

 

네트워크 플로우 최대 유량 문제입니다.

 

소스와 싱크를 만들어 소스 -> 시작장소, 병원 -> 싱크로 연결해 줍시다.

 

각 엣지 별로 단위 시간에 통과할 수 있는 사람 수, 걸리는 시간에 대한 정보를 추가적으로 활용해야합니다.

 

저는 Flow에 대한 정보를 단위시간별로 쪼개서

단위 시간에 통과할 수 있는 사람 수와 현재 시각에 통과한 사람 수를 계산하여 경로를 탐색하였습니다.

 

그러기 위해서 각 엣지별로 Flow에 대한 정보를 단위시간만큼의 배열을 만들어 계산하였고,

단위시간을 관리 하기 위해서 Source에서 0~s 만큼 출발시간을 설정해주어 Network Flow를 진행하였습니다.

 

이렇게 풀이를 하게 될 시 최대 유량이 일행 수를 초과할 수 있으니 조건문으로 잘 걸러주시면 됩니다.

 

정석 풀이는 정점 분할을 이용한 풀이 인것 같으니 정점 분할 풀이에 대한것도 한번 찾아보면 좋을 것 같습니다.

 

 

	#include<iostream>
	#include<algorithm>
	#include<vector>
	#include<queue>
	using namespace std;
	#define Ms 1003
	typedef pair<int, int> pi;
	int t;
	struct MF {
	struct edge {
	int to, c, f[100], t;
	edge *d;
	edge(int to1 = -1, int c1 = 0, int t1 = 0) :to(to1), c(c1), t(t1), d(nullptr) {
	for (int i = 0; i < 100; i++)f[i] = 0;
	}
	int spare(int time) { return c - f[time]; }
	void addFlow(int f1,int time) {
	f[time] += f1;
	d->f[time] -= f1;
	}
	};
	int S = Ms-2, E = Ms - 1, mf = 0, n, g, s, m, r, a, b, c, d, p, T;
	vector<edge*>adj[Ms];
	void init() {
	for (int i = 0; i < Ms; i++)adj[i].clear();
	mf = 0;
	}
	void addEdge(int u, int v, int c, int t) {
	edge *e1 = new edge(v, c, t), *e2 = new edge(u, 0, t);
	e1->d = e2;
	e2->d = e1;
	adj[u].push_back(e1);
	adj[v].push_back(e2);
	}
	int solve() {
	for (int StartTime = 0; StartTime < s&&mf<=g; StartTime++) {
	while (1) {
	int pre[Ms],nowTime=0;
	for (int i = 0; i < Ms; i++)pre[i] = -1;
	edge* path[Ms] = { 0 };
	queue<pi> q;
	q.push({ S,StartTime });
	while (!q.empty()) {
	pi now = q.front();
	q.pop();
	for (edge *e : adj[now.first]) {
	int next = e->to, nxtTime = now.second + e->t;
	if (pre[next] == -1 && e->spare(now.second) > 0 && nxtTime <= s) {
	pre[next] = now.first;
	path[next] = e;
	q.push({ next,nxtTime });
	if (next == E) {
	nowTime = nxtTime;
	break;
	}
	}
	}
	}
	if (pre[E] == -1)break;
	int flow = 1e9, tmpT = nowTime;
	for (int i = E; i != S; i = pre[i]) {
	tmpT -= path[i]->t;
	flow = min(flow, path[i]->spare(tmpT));
	}
	for (int i = E; i != S; i = pre[i]) {
	nowTime -= path[i]->t;
	path[i]->addFlow(flow,nowTime);
	}
	mf += flow;
	if (mf > g)break;
	}
	}
	return mf > g ? g : mf;
	}
	void inp() {
	cin >> n >> a >> g >> s >> m;
	addEdge(S, a, g, 0);
	while (m--) {
	cin >> a;
	addEdge(a, E, Ms, 0);
	}
	cin >> r;
	while (r--) {
	cin >> a >> b >> c >> d;
	addEdge(a, b, c, d);
	}
	cout << solve() << '\n';
	}
	};
	int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> t;
	while (t--) {
	MF m;
	m.init();
	m.inp();
	}
	}

view raw 10319.cpp hosted with ❤ by GitHub