73 wa3个点
查看原帖
73 wa3个点
245085
wenxutong楼主2023/1/27 10:45

不知道为啥wa了3个点,用dinic啥优化都没加

评测:

https://www.luogu.com.cn/record/100582781

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxx 200000000000000000LL
struct point{
	ll x,step;
};
ll n,m,s,t;
ll g[205][205],cen[205],cnt[205];
ll ans=0;
point q[1040005];
bool bfs(){
	memset(cen,-1,sizeof(cen));
	q[1].x=s,q[1].step=1;
	ll f=1,e=1;
	while(f<=e){
		point u=q[f];
		f++;
		if(cen[u.x]!=-1)continue;
		cen[u.x]=u.step;
		for(ll i=1;i<=n;i++){
			if(g[u.x][i]>0&&cen[i]==-1){
				e++;
				q[e].x=i,q[e].step=u.step+1;
			}
		}
	}
	if(cen[t]==-1)return 0;
	return 1;
}
ll dfs(ll now,ll val){
	if(now==t)return val;
	for(ll i=1;i<=n;i++){
		if(g[now][i]>0&&cen[i]==cen[now]+1){
			ll jia=dfs(i,min(val,g[now][i]));
			if(jia>0){
				g[now][i]-=jia;
				g[i][now]+=jia;
				return jia;
			}
		}
	}
	return 0;
}
void dinic(){
	while(1){
		bool flag=bfs();
		if(flag==0)break;
		while(1){
			ll jia=dfs(s,maxx);
			ans+=jia;
			if(jia==0)break;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>s>>t;
	memset(g,0,sizeof(g));
	for(ll i=1;i<=m;i++){
		ll xx,yy,vv;
		cin>>xx>>yy>>vv;
		g[xx][yy]=vv;
	}
	dinic();
	cout<<ans<<"\n";
	return 0;
}
2023/1/27 10:45
加载中...