lao_wang @ 2024-05-06 15:50:28
我的代码
bool bfs(){
for(int i=1;i<=n;i++) now[i] = head[i] , dep[i] = 0x3f3f3f3f3f3f , vis[i] = 0 ;
q.push(s) ;
dep[s] = 0 ;
while(!q.empty()){
int u=q.front() ;
q.pop() ;
vis[u] = 0 ;
for(int i=head[u];~i;i=G[i].next){
int x=G[i].to ;
if(dep[x]<=dep[u]+1||!G[i].w) continue ;
dep[x] = dep[u]+1 ;
if(!vis[x]){
vis[x] = 1 ;
q.push(x) ;
}
}
}
return dep[t]!=0x3f3f3f3f3f3f ;
}
int dfs(int u,int minn){
if(u==t){ vis[u]=1 ;return minn ; }
if(vis[u]) return 0 ;
vis[u] = 1 ;
int use=0 ;
for(int i=now[u];~i;i=G[i].next){
now[u] = i ;
int x=G[i].to ;
if(!G[i].w||dep[x]!=dep[u]+1) continue ;
int temp = dfs(x,min(minn,G[i].w)) ;
if(!temp) continue ;
G[i].w -= temp ;
G[i^1].w += temp ;
use += temp ;
if(use==minn) break;
}
return use ;
}
int dinic(){
long long ans=0 ;
while(bfs()){
int temp=dfs(s,2147483647) ;
ans += temp ;
}
return ans ;
}
其中 dfs(x,min(minn,G[i].w))
原本应该为 dfs(x,min(minn-use,G[i].w))
但是他过了…………
by lao_wang @ 2024-05-14 17:00:54
@stOtue 如果不信可以试试,这种写法就是凭空加流
by lao_wang @ 2024-05-14 17:02:29
@Maxmilite 请问能否使用该题目第一个测点所建出的图作为数据(我下不了测点)
by Otue @ 2024-05-14 17:14:14
@lao_wang 只会导致TLE吧
by lao_wang @ 2024-05-14 17:30:15
@stOtue 怎么可能,这个写法是凭空加流,我写过这道题我能不知道?
by Maxmilite @ 2024-07-08 00:06:30
@lao_wang 我造了一组 hack 数据,现在错误代码应该已经过不了了