@[dengjunhaodejia09](/user/717599) 不是 dinic 吗（
by OldDriverTree @ 2024-01-28 19:03:20
哦，我不太知道 @[OldDriverTree](/user/681036)
by dengjunhaodejia09 @ 2024-01-28 19:04:18
@[dengjunhaodejia09](/user/717599) 你说的是dinic吗（
by cff_0102 @ 2024-01-28 19:10:48
发下代码。我看看。刚学 Dinic（
by RainPPR @ 2024-01-28 19:24:22
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1,ch=getchar();
for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
struct node{
int to,w,nxt;
}e[1919810];
int head[1005],cnt=1;
void add(int x,int y ,int z){
cnt++;
e[cnt].nxt=head[x];
e[cnt].to=y;
e[cnt].w=z;
head[x]=cnt;
}
int lst[1005],Lst[1005],ans,now[1005],bfn[1005];
bool value=false;
int n,m,s,t;
void bfs(int id){
bfn[id]=1;
queue<int> q;
q.push(id);
while(!q.empty()){
int cur=q.front();
q.pop();
now[cur]=head[cur];
for(int i=head[cur];i!=0;i=e[i].nxt){
int v=e[i].to,tot=e[i].w;
if(tot>0 && bfn[v]==0){
bfn[v]=bfn[cur]+1;
q.push(v);
}
}
}
if(bfn[t]==0){
value=false;
}else{
value=true;
}
return;
}
int dfs(int id,int sum){
if(id==t){
return sum;
}
int k=0,sums=0;
for(int i=now[id];i!=0 && sum;i=e[i].nxt){
now[id]=i;
int v=e[i].to,tmp=e[i].w;
if(bfn[v]==bfn[id]+1 && tmp>0){
k=dfs(v,min(sum,tmp));
if(k==0){
bfn[v]=1e17;
}
e[i].w-=k;
e[i^1].w+=k;
sums+=k;
sum-=k;
}
}
return sums;
}
int mp[1005][1005];
signed main(){
int q;
cin>>n>>m>>q;
s=0;
t=n+m+1;
for(int i=1;i<=q;i++){
int x,y,z;
x=read();
y=read();
y+=n;
add(x,y,1);
add(y,x,0);
}
for(int i=1;i<=n;i++){
add(0,i,1);
add(i,0,0);
}
for(int j=1;j<=m;j++){
add(n+j,n+m+1,1);
add(n+m+1,n+j,0);
}
while(1){
value=false;
memset(now,0,sizeof(now));
memset(bfn,0,sizeof(bfn));
bfs(s);
if(value==false){
cout<<ans;
return 0;
}
ans+=dfs(s,1e17);
}
return 0;
}
```
by dengjunhaodejia09 @ 2024-01-28 20:06:39
@[RainPPR](/user/371511)
by dengjunhaodejia09 @ 2024-01-28 20:07:00
@[dengjunhaodejia09](/user/717599) 啊这。你试试 memset 只处理有用的部分。然后 head -> now 的过程用 memcpy 试试。感觉你的代码没有什么问题。
还有一种可能是匈牙利算法复杂度高但是实际上很多数据跑起来真的比 Dinic 要快。这个确实是有的。
by RainPPR @ 2024-01-28 21:01:51
我试了，还是不快但大数据肯定要跑dinic
by dengjunhaodejia09 @ 2024-01-28 21:07:09