[백준]1585 경찰

문제

오세준이 살고 있는 도시에는 사람들의 과속문제가 심각하다. 따라서, 이 도시의 경찰서장은 동호도로에서 과속하는 사람들을 적발하라는 지시를 오세준에게 내렸다. 오세준은 두 개의 속도 측정계를 가져와서 동호도로의 시작과 끝에 설치했다. 그리고, 각각의 차가 동호도로에 들어가는 시간과, 나오는 시간을 기록했다. 오세준은 동호도로에서 과속하는 사람을 쉽게 골라낼 수 있었고, 그 사람들이 벌금을 내게 만들었다.

오세준은 다람쥐를 이용한 불법 도박에 연루된 사실이 밝혀지자 경찰서에서 잘리게 되었다. 오세준은 이대로 잘릴 수 없다고 생각해서, 들어가는 시간과 나오는 시간을 기록한 데이터를 모두 섞어버렸다. 따라서, 정문이는 어떤 들어가는 시간이 어떤 나오는 시간과 일치되는지 알아낼 수 없었다.

정문이는 올해 경찰서의 예산문제 때문에, 벌금을 어떻게든 징수해야 한다. 정문이는 들어간 시간의 정보와 나오는 시간의 정보를 가지고 있다. 그리고, 과속 기준 시간을 가지고 있다. 만약 어떤 차가, 과속 기준 시간보다 작은 시간으로 도로를 통과하면 과속으로 처리한다. (어떤 차가 아무리 빨리 달리더라도 항상 도로를 통과하는 데는 적어도 1초가 걸린다.)

정문이는 들어가는 시간이 나오는 시간보다 이르도록 두 시간을 연관시켜야 한다. 그리고 모든 시간은 단 한 번만 사용할 수 있다. 정문이가 모든 시간을 연관시키고 난 후에는, 각각의 차의 과속 여부를 판별해서 벌금을 징수할 수 있다.

만약 어떤 차가 과속을 했고, 도로를 통과하는데 걸린 시간이 S이고, 과속 기준 시간이 T이면, 정문이는 (T-S)의 제곱만큼 벌금을 징수할 수 있다. (최대 F원, F원을 넘으면 F원의 벌금이 징수된다.) 만약, 과속을 하지 않았으면, 벌금은 징수되지 않는다.

정문이가 징수할 수 있는 벌금의 최솟값과 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 차가 총 몇 대 있는지 주어진다. 이 값을 N이라고 하고, 50보다 작거나 같은 자연수이다. 둘째 줄에는 차가 동호도로에 들어가는 시간이 주어진다. 총 N개의 수가 공백 한 칸을 사이에 두고 주어진다. 셋째 줄에는 차가 동호도로에서 나오는 시간이 주어진다. 마찬가지로 N개의 수가 공백 한 칸을 사이에 두고 주어지며, 모든 시간은 0보다 크거나 같고, 1,000보다 작거나 같은 자연수이다. 넷째 줄에는 과속 기준 시간 T가 주어지고, 다섯째 줄에는 벌금의 최댓값 F가 주어진다. T는 1보다 크거나 같고 1,000보다 작거나 같은 자연수이고, F는 0보다 크거나 같고, 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수 2개를 공백 한 칸으로 구분하여 출력한다. 첫 번째 수는 정문이가 징수할 수 있는 벌금의 최솟값이고, 두 번째 수는 최댓값이다. 만약, 주어진 입력으로 N개의 정보를 만들 수 없으면 -1을 출력한다.

 

MCMF 문제입니다.

자동차의 개수는 N개로 정해져있고,

출발시점과 도착시점은 1대1 대응되어야합니다.

만약 SPFA알고리즘을 수행했는데 유량이 N보다 작다면, N개의 정보를 확정하지 못합니다.

 

fee[i][j]는 i번째 시간출발 j번째 도착시 벌금입니다.

만약 fee[i][j] > 0 이고, fee[j][i] < 0 으로 설정해놓는다면

SPFA에서 

dist[nxt] > dist[cur] + fee[i][j]에 의해,

dist[E]는 최솟값으로 갱신될겁니다. 

왜냐하면 fee[i][j]를 더하면 더할수록 값은 양수로 작아질겁니다.

이를 통해 벌금의 최솟값을 구할 수 있습니다.

 

반면 fee[i][j] < 0 과 fee[j][i] > 0 으로 설정한다면,

SPFA에서

dist[nxt] > dist[cur] + fee[i][j]에 의해, 음수로 계속해서 작아져 가장 작은 음수가 될겁니다.

이에 -1을 곱해주면 벌금의 최댓값을 구할 수 있습니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

using namespace std;
//1~50 entry 시간 
//51~100 out 시간
//101 S ,102 E
int N, c[103][103], f[103][103], S = 101, E = 102, t[103], fee[103][103], T, F, ans;
char mp[51][51];
vi adj[103];
int MCMF() {
	mset(f);
	ans = 0;
	int cnt = 0;
	while (1) {
		queue<int>q;
		q.push(S);
		int p[103], inQ[103], dist[103];
		fill(p, p + 103, -1);
		fill(dist, dist + 103, INF);
		mset(inQ);
		inQ[S] = 1;
		dist[S] = 0;
		while (!q.empty()) {
			int cur = q.front();
			inQ[cur] = 0;
			q.pop();
			for (int nxt : adj[cur]) {
				if (c[cur][nxt] - f[cur][nxt] > 0 && dist[nxt] > dist[cur] + fee[cur][nxt]) {
					dist[nxt] = dist[cur] + fee[cur][nxt];
					p[nxt] = cur;
					if (!inQ[nxt]) {
						q.push(nxt);
						inQ[nxt] = 1;
					}
				}
			}
		}
		if (p[E] == -1)break;
		cnt++;
		for (int i = E; i != S; i = p[i]) {
			ans += fee[p[i]][i];
			f[p[i]][i] += 1;
			f[i][p[i]] -= 1;
		}
	}
	if (cnt < N)return -1;
	return ans;
}
int main() {
	FAST;
	cin >> N;
	int temp1 = -1, temp2 = INT_MAX;
	for (int i = 1; i <= N; i++) {
		cin >> t[i];
		temp1 = max(temp1, t[i]);
		adj[S].push_back(i);
		adj[i].push_back(S);
		c[S][i] = 1;
	}
	for (int i = 51; i <= 50+N; i++) {
		cin >> t[i];
		temp2 = min(temp2, t[i]);
		adj[i].push_back(E);
		adj[E].push_back(i);
		c[i][E] = 1;
	}
	cin >> T >> F;
	for (int i = 1; i <= N; i++) {
		for (int j = 51; j <= 50 + N; j++) {
			if (t[i] < t[j]) {
				adj[i].push_back(j);
				adj[j].push_back(i);
				c[i][j] = 1;
				if (T > t[j] - t[i]) {
					int cost = (int)pow((T - t[j] + t[i]), 2);
					cost = cost >= F ? F : cost;
					fee[i][j] += cost;
					fee[j][i] -= cost;
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if (adj[i].size() == 1) {
			cout << -1;
			return 0;
		}
	}
	int M = MCMF();
	if (M == -1) {
		cout << -1;
		return 0;
	}
	cout << MCMF() << " ";
	for (int i = 1; i <= N; i++) {
		for (int j = 51; j <= 50 + N; j++) {
			fee[i][j] = -fee[i][j];
			fee[j][i] = -fee[j][i];
		}
	}
	cout << -MCMF();
}