QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#670923 | #898. 二分图最大匹配 | yhddd | TL | 4834ms | 50996kb | C++20 | 1.9kb | 2024-10-24 08:49:37 | 2024-10-24 08:49:38 |
Judging History
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 ...