求助,WA on #9~#10
查看原帖
求助,WA on #9~#10
1111034
wfawfas楼主2023/10/21 18:37

下面是源代码,求助

怎么调#9#10都过不了

#include<iostream>
#include<climits>		//‘INT_MAX’ is defined in header ‘<climits>’
#include<cstring>		//‘memset’ is defined in header ‘<cstring>’
#include<queue>
using namespace std;
#define Max 100000
#define LL long long
struct edge
{
	int next;		//同起点的边,连成一条链子
	int to;			//边指向的点
	LL w;			//边的权值
}e[Max];
int head[Max] = { 0 };
int cnt = 0;
void add_edge(int u, int v, LL w)
{
	cnt++;
	e[cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];		//初始时,链子最后的元素.next=0
	head[u] = cnt;

	//建立反向边,使其编号为原边加1
	cnt++;
	e[cnt].to = u;
	e[cnt].w = 0;
	e[cnt].next = head[v];
	head[v] = cnt;
}
int n; int m;
int s, t;
int lv[Max];					
int cur[Max];					
int	bfs()						//bfs进行分层
{
	memset(lv, -1, sizeof(lv));
	lv[s] = 0;
	for (int i = 1; i <= n; i++)
		cur[i] = head[i];
	queue<int> q;
	q.push(s);
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		for (int eg = head[p]; eg; eg = e[eg].next)		
		{
			int to = e[eg].to;
			LL val = e[eg].w;
			if (val > 0 && lv[to] == -1)	
			{
				lv[to] = lv[p] + 1;
				q.push(to);
			}
		}
	}
	return lv[t] != -1;				//判断是否能到达终点
}
LL dfs(int p, LL flow)
{
	if (p == t)
		return flow;
	LL rest = flow;
	for (int eg = cur[p]; eg&&rest; eg = e[eg].next)		//对该点起始的所有边进行遍历
	{
		cur[p] = eg;						//把多次DFS弄到一起
		int to = e[eg].to;
		LL val = e[eg].w;
		if (val>0&&lv[to]==lv[p]+1)			//往深处DFS
		{						
			LL c = dfs(to, min(val,rest));
			rest -= c;				//该点所能流过的流量减少,接着在寻找该点的其他边
			e[eg].w -= c;
			e[eg + 1].w += c;		//保证反向边紧接着正向边建立
			//构造残量网络
		}
	}
	return flow - rest;
}
LL Dinic()

{
	LL Max_Flow = 0;
	while (bfs())
	{
		Max_Flow += dfs(s, LONG_MAX);
	}
	return Max_Flow;
}
int main()
{
	cin >> n >> m;
	cin >> s >> t;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		LL w;
		cin >> u >> v >> w;
		bool temp = true;
		for (int eg = head[u]; eg; eg = e[eg].next)		//对该点起始的所有边进行遍历
			if (e[eg].to == v)
			{
				e[eg].w += w;
				temp = false;
				break;
			}
		if (temp)
			add_edge(u, v, w);
	}
	cout << Dinic();
	return 0;
}
2023/10/21 18:37
加载中...