[백준] 8992 집기 게임

문제

명우는 픽업 게임을 하려고 한다. 규칙은 다음과 같다.

1. 아래 그림과 같은 가로, 세로 선이 여러 개 있다.
2. 선분의 교점을 클릭하면 교점을 이루는 두 선분을 집어갈 수 있다. (집어가면 두 선분은 사라진다)
3. 모든 선분은 무게가 있다.
4. 무게가 a와 b인 선분을 집어갈 때, 얻는 점수는 a × b이다.

게임의 첫 번째 목표는 최대한 많은 선분을 집어가는 것이다. 두 번째 목표는 최대한 많은 점수를 얻는 것이다. 즉, 선분을 많이 집어가는 방법이 여러 가지라면, 점수를 최대로 하는 방법으로 집어가야 한다.

게임의 정보가 주어졌을 때, 집을 수 있는 선분의 최대 개수와, 최대 점수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 가로 선의 수 n과 세로 선의 수 m이 주어진다. (1 ≤ n,m ≤ 200) 다음 n개 줄에는 각 가로 선의 정보 x,y,x',y',w가 주어진다. (x,y)와 (x',y')는 선분의 양 끝 점을 나타내고, w는 그 선분의 무게이다. (y = y') 다음 m개 줄에는 세로 선의 정보가 가로 선의 정보와 같은 형식으로 주어진다. 모든 좌표는 양수이고 100,000보다 작거나 같다. 또한, 무게도 양수이며 20보다 작거나 같다. 모든 선분 쌍은 최대 한 개의 점에서 만나며, 끝 점에서 만나는 경우는 없다.

출력

각 테스트 케이스마다 두 정수를 출력한다. 첫 정수는 집을 수 있는 선분의 쌍의 개수의 최댓값이고, 두 번째는 그 쌍의 개수만큼을 집어가면서 얻을 수 있는 최대 점수이다.

 

가로줄과 세로줄을 나누어 소스와 가로줄을 연결하고, 세로줄과 싱크를 연결합니다.

세로줄과 가로줄이 교접한다면, 그 세로줄과 가로줄을 연결합니다.

이분그래프를 만들어주면 MCMF문제가 됩니다.

#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~200 가로줄
//201~400 세로줄
//401 소스
//402 싱크
int c[403][403], f[403][403],weight[403][403], S = 401, E = 402;
vi adj[403];
struct line {
	int idx;
	int x1, y1, x2, y2, w;
};
vector<line>R;
vector<line>C;
bool isCrossed(line a, line b) {
	//a 가로줄 
	//b 세로줄
	if (a.x1 <= b.x1 && b.x1 <= a.x2 && a.y1 <= b.y2 && b.y1 <= a.y1)
		return true;
	return false;
}
void MCMF() {
	int MAXLINE = 0, MAXWEIGHT = 0;
	while (1) {
		queue<int>q;
		q.push(S);
		int p[403], inQ[403], dist[403];
		fill(p, p + 403, -1);
		fill(dist,dist + 403, INF);
		mset(inQ);
		dist[S] = 0;
		while (!q.empty()) {
			int cur = q.front();
			inQ[cur] = 0;
			q.pop();
			for (auto nxt : adj[cur]) {
				if (dist[nxt] > dist[cur] + weight[cur][nxt] && c[cur][nxt] - f[cur][nxt] > 0) {
					dist[nxt] = dist[cur] + weight[cur][nxt];
					p[nxt] = cur;
					if (!inQ[nxt]) {
						q.push(nxt);
						inQ[nxt] = 1;
					}
				}
			}
		}
		if (p[E] == -1)break;
		MAXLINE++;
		for (int i = E; i != S; i = p[i]) {
			MAXWEIGHT-= weight[p[i]][i];
			f[p[i]][i] += 1;
			f[i][p[i]] -= 1;
		}
	}
	cout << MAXLINE << " " << MAXWEIGHT << "\n";
}
int main() {
	FAST;
	int TC, N, M, x1, y1, x2, y2, w;
	cin >> TC;
	while (TC--){
		R.clear();
		C.clear();
		mset(c);
		mset(f);
		mset(weight);
		REP(i, 402)adj[i].clear();

		cin >> N >> M;
		REP(i, N) {
			cin >> x1 >> y1 >> x2 >> y2 >> w;
			if(x1<x2)
				R.push_back({ i,x1,y1,x2,y2,w });
			else
				R.push_back({i,x2,y1,x1,y2,w });
			c[S][i] = 1;
			adj[S].push_back(i);
			adj[i].push_back(S);
		}
		REP(i, M) {
			cin >> x1 >> y1 >> x2 >> y2 >> w;
			if(y1<y2)
				C.push_back({ i+200,x1,y1,x2,y2,w });
			else
				C.push_back({ i+200,x1,y2,x2,y1,w });
			c[i+200][E] = 1;
			adj[i+200].push_back(E);
			adj[E].push_back(i+200);
		}
		for (line ro : R) {
			for (line co: C) {
				if (isCrossed(ro, co)) {
					c[ro.idx][co.idx] = 1;
					adj[ro.idx].push_back(co.idx);
					adj[co.idx].push_back(ro.idx);

					weight[ro.idx][co.idx] = -(ro.w * co.w);
					weight[co.idx][ro.idx] = (ro.w * co.w);
				}
			}
		}
		MCMF();
	}
}