QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#670923#898. 二分图最大匹配yhdddTL 4834ms50996kbC++201.9kb2024-10-24 08:49:372024-10-24 08:49:38

Judging History

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

  • [2024-10-24 08:49:38]
  • 评测
  • 测评结果:TL
  • 用时:4834ms
  • 内存:50996kb
  • [2024-10-24 08:49:37]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define db double
using namespace std;
const int maxn=2000010;
const int inf=1e18;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n,m,k;
struct nd{
	int nxt,to,w;
}e[maxn<<1];
int head[maxn],tot=1,s,t;
void add(int u,int v,int w){
	e[++tot]={head[u],v,w};head[u]=tot;
	e[++tot]={head[v],u,0};head[v]=tot;
}
int rad[maxn],dis[maxn];
queue<int> q;
bool bfs(){
	for(int i=1;i<=t;i++)rad[i]=head[i],dis[i]=0;
	dis[s]=1;q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(!dis[v]&&e[i].w)dis[v]=dis[u]+1,q.push(v);
		}
	}
	return dis[t];
}
int dfs(int u,int res){
	if(u==t)return res;
	int cnt=0;
	for(int i=rad[u];i;i=e[i].nxt){
		int v=e[i].to;rad[u]=i;
		if(dis[v]==dis[u]+1&&e[i].w){
			int out=dfs(v,min(e[i].w,res));
			e[i].w-=out;e[i^1].w+=out;
			cnt+=out;res-=out;
			if(!res)break;
		}
	}
	return cnt;
}
void work(){
	n=read();m=read();k=read();s=n+m+1,t=n+m+2;
	for(int i=1;i<=k;i++){
		int u=read()+1,v=read()+1;
		add(u,v+n,1);
	}
	for(int i=1;i<=n;i++)add(s,i,1);
	for(int i=1;i<=m;i++)add(i+n,t,1);
	int flow=0;while(bfs())flow+=dfs(s,inf);
	printf("%lld\n",flow);
	for(int i=2;i<=2*k;i+=2)if(!e[i].w){
		int u=e[i^1].to,v=e[i].to;
		printf("%lld %lld\n",u-1,v-n-1);
	}
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=1;
	while(T--)work();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4834ms
memory: 39228kb

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
78474 45795
92549 13903
73460 34144
96460 92850
76342 51542
76410 89381
1778 61392
43607 96135
84268 74827
19876 174
1481 94390
12423 55019
64368 92587
81295 7902
25432 46032
7004 23282
29100 60189
70797 28664
49166 48275
56159 7961
23562 76094
4507 80396
70329 91264
41532 61133
3580 43660
44...

result:

ok OK

Test #2:

score: 0
Accepted
time: 4302ms
memory: 36416kb

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:

100000
56815 52516
40377 1757
50463 66496
15833 50879
9828 16330
80692 9962
51095 17590
90774 57492
44786 41895
3386 35478
84803 93635
90745 34876
7472 34257
36580 19532
8821 61870
41395 2585
99666 33504
90496 2775
8128 71333
85506 34046
65629 62628
15022 71577
7538 82555
64524 72576
33208 93167
531...

result:

ok OK

Test #3:

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

input:

4 4 7
1 1
2 2
0 0
3 1
1 2
2 0
3 2

output:

3
1 1
2 0
3 2

result:

ok OK

Test #4:

score: 0
Accepted
time: 54ms
memory: 50996kb

input:

100000 100000 199999
25370 25370
85964 85963
415 415
16796 16796
12437 12437
45409 45408
63005 63004
22155 22155
87828 87827
84013 84013
37307 37307
72324 72324
83703 83703
55390 55389
6780 6779
78090 78090
9375 9375
82192 82192
74694 74694
49841 49841
15798 15798
69855 69854
82948 82947
97389 97388...

output:

100000
25370 25370
415 415
16796 16796
12437 12437
22155 22155
84013 84013
37307 37307
72324 72324
83703 83703
78090 78090
9375 9375
82192 82192
74694 74694
49841 49841
15798 15798
36770 36770
27645 27645
50147 50147
73191 73191
47835 47835
80563 80563
22103 22103
12751 12751
24922 24922
15168 15168...

result:

ok OK

Test #5:

score: 0
Accepted
time: 75ms
memory: 50984kb

input:

100000 100000 199999
59469 59469
76773 76772
89516 89516
87040 87040
90184 90184
83075 83075
61454 61454
33615 33615
85794 85793
92072 92071
49725 49725
63842 63841
99247 99247
24121 24121
29552 29551
73533 73533
75845 75845
27029 27028
84418 84418
26636 26636
10100 10099
75013 75012
67341 67341
756...

output:

100000
59469 59469
89516 89516
87040 87040
90184 90184
83075 83075
61454 61454
33615 33615
49725 49725
99247 99247
24121 24121
73533 73533
75845 75845
84418 84418
26636 26636
67341 67341
32504 32504
5752 5752
41749 41749
33184 33184
70841 70841
98815 98815
3265 3265
57647 57647
24293 24293
89920 899...

result:

ok OK

Test #6:

score: -100
Time Limit Exceeded

input:

100000 100000 199999
22284 45795
32144 44930
58734 13903
57136 34144
7548 92850
56318 11874
77529 85278
27039 51542
77506 94257
69265 89381
67073 61392
86159 96135
83227 74827
14857 19500
32084 73639
86884 174
27268 94390
20020 55019
45357 92587
17833 7902
55801 46032
36293 46557
73555 13746
8418 88...

output:

100000
22284 45795
58734 13903
57136 34144
7548 92850
27039 51542
69265 89381
67073 61392
86159 96135
83227 74827
86884 174
27268 94390
20020 55019
45357 92587
17833 7902
55801 46032
73310 23282
89482 60189
60485 28664
2721 48275
89892 7961
24437 76094
58192 80396
28938 91264
6101 61133
70994 43660
...

result: