Dinic TLE求助(悬赏关注)
查看原帖
Dinic TLE求助(悬赏关注)
536439
YONIC楼主2022/5/21 08:33

建图时tot设0会WA#11,但是#9#10AC,设1会TLE#9#10,但#11AC

#include<bits/stdc++.h>
#define int long long
#define M 203
#define M2 (int)(5e3+3)
using namespace std;
int n,m,s,t,now,ans,dep[M<<1],l,r;
queue<int>Q;
bool vis[M];
class graph{
	public:
		int tot=1,head[M<<1];
		class edge{
			public:
				int nxt,to,w;
		};
		edge h[M2<<1];
		void add(int u,int v,int w){
			h[++tot].to=v;
			h[tot].nxt=head[u];
			h[tot].w=w;
			head[u]=tot;
		}
};
graph G;
bool BFS(){
	memset(dep,0,sizeof(dep));
	Q.push(s);
	dep[s]=1;
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		for(int i=G.head[x];i;i=G.h[i].nxt){
			int y=G.h[i].to;
			if(G.h[i].w&&!dep[y]){ 
				dep[y]=dep[x]+1;
				Q.push(y);
			}
		}
	}
	return dep[t];
}
int DFS(int x,int in){
    if(x==t) return in;
    int out=in;
    for(int i=G.head[x];i&&out;i=G.h[i].nxt){
        int y=G.h[i].to;
        if(G.h[i].w&&dep[y]==dep[x]+1) {
            int res=DFS(y,min(G.h[i].w,out));
            G.h[i].w-=res;
            G.h[i^1].w+=res;
            out-=res;
            if(!out) break;
        }
    }
    if(!out) dep[x]=0;
    return in-out;
}
signed main(){
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	for(int i=1,u,v,w;i<=m;++i){
		scanf("%lld%lld%lld",&u,&v,&w);
		G.add(u,v,w);
		G.add(v,u,0);
	}
	while(BFS()) ans+=DFS(s,1e18);
	printf("%lld\n",ans);
	return 0;
}
2022/5/21 08:33
加载中...