QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#92039#898. 二分图最大匹配DaBenZhongXiaSongKuaiDi#TL 4995ms29960kbC++141.6kb2023-03-30 09:32:552023-03-30 09:33:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 09:33:04]
  • 评测
  • 测评结果:TL
  • 用时:4995ms
  • 内存:29960kb
  • [2023-03-30 09:32:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = (int)2e5+5;
int n,m,s,t,L,R,lev[maxn],h[maxn]; queue<int> q;
struct Node{int to,c,rev;}; vector<Node> v[maxn];
void addEdge(int fr,int to,int c){
	int f=v[fr].size(), g=v[to].size();
	v[fr].push_back((Node){to,c,g}), v[to].push_back((Node){fr,0,f});
}
bool bfs(){
	while(!q.empty()) q.pop();
	for(int al=0;al<=n;al++) lev[al] = -1, h[al] = 0;
	lev[s] = 0; q.push(s);
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(auto X:v[u])if(X.c && lev[X.to]==-1)
			lev[X.to] = lev[u]+1, q.push(X.to);
		if(~lev[t]) return 1;
	}
	return lev[t]!=-1;
}
int dfs(int u,int k){
	if(u==t || !k) return k;
	int ret = 0, sz = v[u].size();
	for(int al=h[u];al<sz;al++,h[u]=al)if(v[u][al].c){
		int to = v[u][al].to;
		if(lev[to]==lev[u]+1){
			int cur = dfs(to,min(k,v[u][al].c));
			v[u][al].c -= cur, v[to][v[u][al].rev].c += cur;
			k -= cur, ret += cur;
			if(!k) break;
		}
	}
	if(!ret) lev[u] = -1;
	return ret;
}
int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d%d%d",&L,&R,&m);
	s = 0, t = n = L+R+1; 
	for(int al=1;al<=L;al++) addEdge(0,al,1);
	for(int al=1;al<=R;al++) addEdge(al+L,L+R+1,1);
	for(int al=1,be,ga;al<=m;al++)
		scanf("%d%d",&be,&ga), addEdge(be+1,ga+L+1,1);
	ll ans = 0;
	while(bfs()) ans += dfs(s,INT_MAX);//, printf("fr %lld\n",ans);
	printf("%lld\n",ans);
	for(int al=1;al<=L;al++)for(auto X:v[al])if(X.to>L && !X.c){printf("%d %d\n",al-1,X.to-L-1);break;}
//	printf("%.3lf\n",(double)clock()/(double)CLOCKS_PER_SEC);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4995ms
memory: 29960kb

input:

100000 100000 200000
78474 45795
32144 46392
92549 13903
73460 34144
96460 92850
56318 77066
77529 84436
76342 51542
77506 99268
76410 89381
1778 61392
43607 96135
84268 74827
14857 35966
32084 94908
19876 174
1481 94390
12423 55019
64368 92587
81295 7902
25432 46032
36293 61128
73555 84836
8418 102...

output:

100000
0 54731
1 26066
2 89637
3 1717
4 68505
5 28330
6 55261
7 34703
8 42170
9 23249
10 90437
11 69580
12 72086
13 47593
14 29944
15 87183
16 763
17 2814
18 46044
19 75228
20 11487
21 72701
22 60611
23 36775
24 66081
25 45592
26 3321
27 88211
28 71467
29 47516
30 55528
31 83162
32 46298
33 26459
34...

result:

ok OK

Test #2:

score: -100
Time Limit Exceeded

input:

100000 100000 200000
56815 52516
2576 76201
40377 1757
50463 66496
15833 50879
9828 16330
80692 9962
51095 17590
15870 35191
91301 65509
90774 57492
11890 8966
44786 41895
3386 35478
93470 47452
84803 93635
90745 34876
18201 38717
7472 34257
36580 19532
13248 27524
6441 69869
8821 61870
94536 67713
...

output:


result: