백준8992 집기 게임

작성일 | In

문제 링크

  • http://icpc.me/8992

문제 출처

  • 2013 대전 리저널 인터넷 예선 I번

사용 알고리즘

  • 선분 교차
  • MCMF

풀이

각 선분들을 정점으로 잡고, 교차하는 선분들을 간선으로 이어준 형태의 그래프를 봅시다.
MCMF 문제로 바뀌게 됩니다.

ccw로 선분 교차 판정하는 것과 MCMF를 잘 짜면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

struct Segment{
	p x, y;
	int w;
};

int n, m;
int bias = 200;
const int s = 401, t = 402;

int c[444][444];
int f[444][444];
int d[444][444];
vector<int> g[444];

vector<Segment> a, b;

void init(){
	a.clear(); b.clear();
	a.resize(1); b.resize(1);
	memset(c, 0, sizeof c);
	memset(f, 0, sizeof f);
	memset(d, 0, sizeof d);
	for(int i=0; i<444; i++) g[i].clear();
}

void addEdge(int s, int e, int x){
	x *= -1;
	c[s][e] = 1; d[s][e] = x; g[s].push_back(e);
	d[e][s] = -x; g[e].push_back(s);
}

bool chk(int i, int j){

//	cout << "a : " << a[i].x.x << " " << a[i].x.y << " / " << a[i].y.x << " " << a[i].y.y << "\n";
//	cout << "b : " << b[j].x.x << " " << b[j].x.y << " / " << b[j].y.x << " " << b[j].y.y << "\n";

	int x = a[i].x.x, xx = a[i].y.x;
	if(x > xx) swap(x, xx);
	if(b[j].x.x < x || xx < b[j].x.x) return 0;
	int y = b[j].x.y, yy = b[j].y.y;
	if(y > yy) swap(y, yy);
	if(a[i].x.y < y || yy < a[i].x.y) return 0;
//	cout << "cross\n";
	return 1;
}

void solve(){
	init();
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		Segment now;
		cin >> now.x.x >> now.x.y >> now.y.x >> now.y.y >> now.w;
		a.push_back(now);
	}
	for(int i=1; i<=m; i++){
		Segment now;
		cin >> now.x.x >> now.x.y >> now.y.x >> now.y.y >> now.w;
		b.push_back(now);
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(chk(i, j)) addEdge(i, j+bias, a[i].w * b[j].w);
		}
	}
	for(int i=1; i<=n; i++) addEdge(s, i, 0);
	for(int i=1; i<=m; i++) addEdge(i+bias, t, 0);

	int cnt = 0;
	int ans = 0;
	while(1){
		int par[444]; memset(par, -1, sizeof par);
		int inq[444]; memset(inq, 0, sizeof inq);
		int dst[444]; memset(dst, 0x3f, sizeof dst);

		queue<int> q;
		q.push(s); inq[s] = 1; dst[s] = 0;
		while(q.size()){
			int now = q.front(); q.pop(); inq[now] = 0;
			for(auto nxt : g[now]){
				if(c[now][nxt] - f[now][nxt] > 0 && dst[nxt] > dst[now] + d[now][nxt]){
					dst[nxt] = dst[now] + d[now][nxt];
					par[nxt] = now;
					if(!inq[nxt]){
						inq[nxt] = 1; q.push(nxt);
					}
				}
			}
		}
		if(par[t] == -1) break;
		cnt++;
		int fl = 1e9;
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			fl = min(fl, c[a][b] - f[a][b]);
		}
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			ans += d[a][b] * fl;
			f[a][b] += fl, f[b][a] -= fl;
		}
	}
	cout << cnt << " " << -ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	for(int i=1; i<=t; i++){
		solve();
	}
}