QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#218050#6546. Greedy Bipartite MatchingzhoukangyangTL 3ms13508kbC++112.3kb2023-10-17 17:48:242023-10-17 17:48:24

Judging History

你现在查看的是最新测评结果

  • [2023-10-17 17:48:24]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:13508kb
  • [2023-10-17 17:48:24]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long 
using namespace std;
const int N = 2e5 + 7, inf = 1e9;
int n, m, q;
ll ans;

vi e[N];
int matl[N], matr[N], disl[N], disr[N];
bool bfs() {
	L(i, 1, n) 
		disl[i] = inf, disr[i] = inf;
	queue < int > q;
	L(i, 1, n)
	 	if(!matl[i]) 
	 		disl[i] = 0, q.push(i);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(auto&v : e[u]) 
			if(disr[v] > disl[u] + 1) {
				disr[v] = disl[u] + 1;
				if(matr[v]) 
					disl[matr[v]] = disr[v], q.push(matr[v]);
			}
	}
	L(i, 1, n) 
		if(!matr[i] && disr[i] < inf)
			return true;
	return false;
}

int visr[N], visl[N];
int dfs(int x, int mnd) {
	if(disl[x] >= mnd) 
		return false;
	if(visl[x]) 
		return false;
	visl[x] = true;
	for(auto&v : e[x]) {
//		cout << x << " -> " << v << ' ' << disr[v] << ' ' << visr[v] << endl;
		if(disr[v] == disl[x] + 1 && !visr[v]) {
//			cout << x << " -> " << v << ' ' << matr[v] << endl;
			visr[v] = true;
			if(!matr[v] || dfs(matr[v], mnd)) {
				matr[v] = x, 
				matl[x] = v;
				return true;
			}
		}
	}
	return false;
}

int stk[N], top;
int main () {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> q;
	
	int ans = 0;
	while(q--) {
		int m;
		cin >> m;
		while(m--) {
			int x, y;
			cin >> x >> y;
			e[x].emplace_back(y);
		}
		while(bfs()) {
			L(i, 1, n) visl[i] = false, visr[i] = false;
			int mn = inf;
			L(i, 1, n) if(!matr[i]) mn = min(mn, disr[i]);
			int win = 0;
			L(x, 1, n) 
				if(!matl[x] && disl[x] == 0 && dfs(x, mn)) {
					++ans;
					win = 1;
					break;
				}
			if(!win) {
				assert(false);
			}
//			cout << endl;
//			L(i, 1, n) {
//				cout << matl[i] << ' ' << matr[i] << endl;
//			}
		}
		L(u, 1, n) if(disl[u] == inf) {
			top = 0;
			L(p, 0, sz(e[u]) - 1) {
				int v = e[u][p];
				if(disr[v] < inf) {
					stk[++top] = p;
				}
			}
			R(i, top, 1) {
				e[u].erase(e[u].begin() + stk[i]);
			}
		}
		cout << ans << ' ';
	}
	return 0;
} 
/*
3 2
1
1 1
2
2 1
1 2
*/

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 13508kb

input:

3 4
2
1 1
1 2
2
1 1
2 2
2
1 3
3 2
1
3 3

output:

1 2 2 3 

result:

ok 4 number(s): "1 2 2 3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 8512kb

input:

0 0

output:


result:

ok 0 number(s): ""

Test #3:

score: 0
Accepted
time: 0ms
memory: 13216kb

input:

2 2
0
2
1 2
1 2

output:

0 1 

result:

ok 2 number(s): "0 1"

Test #4:

score: -100
Time Limit Exceeded

input:

100000 1
200000
78475 45796
32145 46393
92550 13904
73461 34145
96461 92851
56319 77067
77530 84437
76343 51543
77507 99269
76411 89382
1779 61393
43608 96136
84269 74828
14858 35967
32085 94909
19877 175
1482 94391
12424 55020
64369 92588
81296 7903
25433 46033
36294 61129
73556 84837
8419 10215
12...

output:


result: