测样例的时候卡死了
查看原帖
测样例的时候卡死了
757946
gaolangwen_is_sb楼主2023/5/5 19:01

rt,用的Dinic,写了调试代码,发现是bfs一直等于true

求助!

#include<bits/stdc++.h>
using namespace std;

const int N=205,mx=0x3f3f3f3f;
int n,m,s,t,ans,dis[N];
struct Node
{
	int to,w;
};
vector<Node>nbr[N];

bool bfs()
{
	queue<int>q;
	memset(dis,0x3f,sizeof dis);
	int cur=s;
	q.push(cur);
	dis[s]=0;
	while(!q.empty())
	{
		cur=q.front();
		q.pop();
		for(int i=0;i<nbr[cur].size();i++)
		{
			int nxt=nbr[cur][i].to,w=nbr[cur][i].w;
			if(dis[nxt]==mx&&w>0)
			{
				q.push(nxt);
				dis[nxt]=dis[cur]+1;
				if(nxt==t)
					return true; 
			}
		}
	}
	return false;
}

int dfs(int x,int sum)
{
	if(x==t)
		return sum;
	int num=0;
	for(int i=0;i<nbr[x].size();i++)
	{
		int nxt=nbr[x][i].to,w=nbr[x][i].w;
		if(dis[x]+1==dis[nxt]&&w>0)
		{
			int val=dfs(nxt,min(sum,w));
			nbr[x][nxt].w-=val;
			nbr[nxt][x].w+=val;
			num+=val;
			sum-=val;
		}
	}
	return num;
}

int main()
{
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		nbr[x].push_back((Node){y,w});
		nbr[y].push_back((Node){x,0});
	}
	while(bfs()==true)
	{
		ans+=dfs(s,mx);
	}
	cout<<ans;
	return 0;
}
2023/5/5 19:01
加载中...