91 pts
查看原帖
91 pts
549499
Disjoint_cat楼主2023/1/20 09:26

难道是我当前弧假了???

核心代码:

const int N=205,M=5005;
int n,m,s,t;
int U,V;ll Cap;
int head[N],to[M<<1],nxt[M<<1],tot,nxte[N];ll cap[M<<1];
#define rev(x) ((x&1)?x+1:x-1)
void add()
{
	to[++tot]=V,cap[tot]=Cap,nxt[tot]=head[U],head[U]=tot;
	to[++tot]=U,cap[tot]=0,nxt[tot]=head[V],head[V]=tot;
}
int lev[N];bool vis[N];
void bfs()
{
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)nxte[i]=head[i];
	queue<int>q;
	q.push(s);
	while(q.size())
	{
		int now=q.front();q.pop();
		vis[now]=1;
		for(int i=head[now];i;i=nxt[i])
		{
			int To=to[i];
			if(!cap[i]||vis[To])continue;
			lev[To]=lev[now]+1;
			q.push(To);
		}
	}
}
vector<int>E;
ll dfs(int now)
{
	if(now==t)return 1000000000000000000;
	for(int i=nxte[now];i;i=nxt[i],nxte[now]=i)
	{
		if(!cap[i]||lev[to[i]]<=lev[now])continue;
		ll flo=dfs(to[i]);
		if(flo){E.push_back(i);return min(cap[i],flo);}
	}
	return 0;
}
ll Dinic()
{
	ll ans=0;//int cnt=0;
	while(1)
	{
		//cout<<++cnt<<endl;
		bfs();
		if(!vis[t])break;
		while(1)
		{
			E.clear();
			ll flow=dfs(s);
			if(!flow)break;
			ans+=flow;
			for(int i=0;i<E.size();i++)
				cap[E[i]]-=flow,cap[rev(E[i])]+=flow;
		}
	}
	return ans;
}
void Solve()
{
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		cin>>U>>V>>Cap;
		add();
	}
	cout<<Dinic();
}
2023/1/20 09:26
加载中...