一些疑问,关于炸点
查看原帖
一些疑问,关于炸点
507348
__vector__楼主2023/3/7 17:09

我的代码加上第 74 行的标记点无法到达终点后,AC,不加上就 TLE。

删掉 74 行加上当前弧优化也能 A

但是不加上这个复杂度也是对的,为啥还 T。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e16;
const int maxn=205;
const int maxm=5005;
int head[maxn];
struct EDGE
{
	int to,nxt;
	ll val;
}edge[maxm<<1];
int cnt=1;
void add(int u,int to,int val)
{
	edge[++cnt].to=to;
	edge[cnt].val=val;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
int n,m,s,t;
ll dis[maxn];
bool inq[maxn];
bool bfs()
{
	memset(inq,0,sizeof inq);
	for(int i=0;i<=n;i++)
	{
		dis[i]=1e18;
	}
	dis[s]=0;
	queue<int> que;
	que.push(s);
	while(!que.empty())
	{
		int u=que.front();
		que.pop();
		inq[u]=0;
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(edge[i].val)
			{
				if(dis[to]>dis[u]+1)
				{
					dis[to]=dis[u]+1;
					if(!inq[to])
					{
						que.push(to);
						inq[to]=1;
					}
				}
			}
		}
	}
	return (dis[t]!=dis[0]);
}
ll dfs(int u,ll flow)
{
	if(u==t)return flow;
	ll used=0;
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int to=edge[i].to;
		if(edge[i].val&&dis[to]==dis[u]+1)
		{
			ll useflow=dfs(to,min(flow-used,edge[i].val));
			edge[i].val-=useflow;
			edge[i^1].val+=useflow;
			used+=useflow;
		}
		if(flow==used)break;
	}
	if(!used)dis[u]=-1;
	return used;
}
void Dinic()
{
	ll ans=0;
	while(bfs())
	{
		ans+=dfs(s,inf);
	}
	printf("%lld",ans);
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
		add(u,v,c);
		add(v,u,0);
	}
	Dinic();
	return 0;
}  
2023/3/7 17:09
加载中...