QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#92039 | #898. 二分图最大匹配 | DaBenZhongXiaSongKuaiDi# | TL | 4995ms | 29960kb | C++14 | 1.6kb | 2023-03-30 09:32:55 | 2023-03-30 09:33:04 |
Judging History
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 ...