Dinic T了5个点 求助
查看原帖
Dinic T了5个点 求助
257206
Herio楼主2020/6/30 18:08
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200+10,M=1e4+5,mod=1e9+7;
const ll inf=1e15;
#define mst(a) memset(a,0,sizeof a)
#define fmst(a) memset(a,-1,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int n,m,s,t,h[M],cur[M],cnt,dep[M];
struct node{
	int to,nt;
	ll w;
}e[M];
void add(int u,int v,ll w){
	e[cnt]={v,h[u],w};
	h[u]=cnt++;
}
bool bfs(){
	fmst(dep);
	queue<int>q;
	dep[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=h[u];~i;i=e[i].nt){
			int v=e[i].to;
			ll w=e[i].w;
			if(dep[v]==-1&&w)
				dep[v]=dep[u]+1,q.push(v);
		}
	}
	return dep[t]!=-1;
}
ll dfs(int u,ll flow){
	if(u==t) return flow;
	ll delta=flow;
	for(int i=cur[u];~i;i=e[i].nt){
		cur[u]=e[i].nt;
		int v=e[i].to;
		ll w=e[i].w;
		if(dep[v]==dep[u]+1&&e[i].w>0){
			ll x=dfs(v,min(flow,1LL*e[i].w));
			e[i].w-=x,e[i^1].w+=x;
			delta-=x;
			if(!delta) break;
		}
	}
	return flow-delta;
}
ll dinic(){
	ll ans=0;
	while(bfs()){
		for(int i=1;i<=n;i++)
			cur[i]=h[i];
		ans+=dfs(s,inf);
	}
	return ans;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	fmst(h);
	for(int i=1;i<=m;i++){
		int u,v;
		ll w;
		scanf("%d%d%lld",&u,&v,&w);
		add(u,v,w);
		add(v,u,0);
	}
	printf("%lld\n",dinic());
	return 0;
}

不知道哪里出了问题,有人能帮帮我吗。

2020/6/30 18:08
加载中...