[백준] 1258 문제 할당

문제

N명의 학생들에게 N개의 문제가 출제되었다. 학생들은 각자 한 문제씩을 할당받아 그 문제만을 풀려고 한다. 즉, 모든 학생이 서로 다른 문제를 하나씩 맡아서 푸는 것이다.

 문제 1문제 2문제 3

학생 1	1	3	3
학생 2	2	3	3
학생 3	3	2	4

모든 학생들은 서로 잘 풀 수 있는 문제가 다르기 때문에, 각 문제마다 문제를 푸는 데 걸리는 시간이 다를 수가 있다. 예를 들어 위의 표처럼 문제 1을 푸는 데 학생 1은 1시간이 걸리지만, 학생2는 2시간이 걸린다.

우리는 모든 학생들이 문제를 푸는 데 걸리는 시간의 총 합을 최소화하고 싶다. 예를 들어 학생 1이 문제 1을 풀고, 학생 2가 문제 3을 풀고, 학생 3이 문제 2를 풀면, 문제를 푸는 데 걸리는 시간의 합은 1 + 3 + 2 = 6이 된다. 문제를 푸는 데 걸리는 시간을 이보다 더 짧게 할 수는 없다.

N명의 학생이 N개의 문제를 푸는 데 걸리는 시간이 모두 주어졌을 때, 각 학생에게 서로 다른 문제를 하나씩 할당하여, 문제를 푸는 데 걸리는 시간의 총 합을 최소화하는 프로그램을 작성하시오.

입력

첫째 줄에는 N(1 ≤ N ≤ 100)이 주어지고, 둘째 줄부터 N개의 줄에 걸쳐 각 학생이 N개의 문제를 푸는 데 걸리는 시간을 나타내는 N개의 정수가 순서대로 주어진다. 주어지는 모든 정수는 1,000을 넘지 않는다.

출력

각 학생에게 서로 다른 문제를 하나씩 할당하여, 문제를 푸는 데 걸리는 시간의 총 합의 최솟값을 출력한다.

 

N명의 학생이 N개의 문제를 각각 하나씩 풀어야합니다.

소스에서 각 사람으로 가는 capacity와 각 문제에서 싱크로가는 capacity , 그리고 각 사람에서 문제로가는 capacity는 모두 1입니다.

MCMF문제입니다.

SPFA를 사용합니다.

#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;
int N, c[203][203], f[203][203], cost[203][203], S = 201, E = 202, ans;
vi adj[203];
//1~100 사람 101~200 문제 소스:201 싱크: 202
int main() {
	FAST;
	cin >> N;
	REP(i, N)REP(j, N) {
		cin >> cost[i][j+100];
		cost[j + 100][i] = -cost[i][j + 100];
		c[i][j+100] = 1;

		adj[i].push_back(j + 100);
		adj[j + 100].push_back(i);
	}
	REP(i, N) {
		c[S][i] = 1;
		c[i+100][E] = 1;

		adj[S].push_back(i);
		adj[i].push_back(S);

		adj[i + 100].push_back(E);
		adj[E].push_back(i + 100);
	}
	while (1) {
		queue<int>q;
		int inQ[203], p[203], dist[203];
		mset(inQ);
		fill(p, p + 203, -1);
		fill(dist, dist + 203, INF);
		q.push(S);
		dist[S] = 0;
		while (!q.empty()) {
			int cur = q.front();
			inQ[cur] = 0;
			q.pop();
			for(int i:adj[cur]) {
				if (c[cur][i] - f[cur][i] > 0 && dist[i] > dist[cur] + cost[cur][i]) {
					dist[i] = dist[cur] + cost[cur][i];
					p[i] = cur;
					if (!inQ[i]) {
						q.push(i);
						inQ[i] = 1;
					}
				}
			}
		}
		if (p[E] == -1)break;
		for (int i = E; i != S; i = p[i]) {
			ans += cost[p[i]][i];
			f[p[i]][i] += 1;
			f[i][p[i]] -= 1;
		}
	}
	cout << ans;
}