有个小疑问
查看原帖
有个小疑问
339299
osfly楼主2022/6/28 22:04

在这份代码中

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,s,t;
struct edge
{
	int v;
	int nxt;
	int w;
}e[5010<<1];
int head[1000],tot=1;
long long maxn=0;
void add(int u,int v,int w)
{
	e[++tot].v=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}
int d[1000];
int cur[1000];
bool bfs()
{
	memset(d,0,sizeof(d));
	queue<int> q;
	d[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			int w=e[i].w;
			if(!d[v]&&w)
			{
				d[v]=d[u]+1;
				q.push(v);
				if(v==t) return 1;	
			}
		}
	}
	return 0;
}
int dfs(int u,int flow)
{
	if(u==t) return flow;
	int rest=flow;
	for(int i=cur[u];i&&rest;i=e[i].nxt)
	{
		cur[u]=i;
		int v=e[i].v;
		int w=e[i].w;
		if(w&&d[v]==d[u]+1)
		{
			int k=dfs(v,min(rest,w));
			if(!k) d[v]=0;
			e[i].w-=k;
			e[i^1].w+=k;
			rest-=k;	
		}
	 } 
	return flow-rest;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1,u,v,w;i<=m;i++)
	{
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
    }
    int flow=0;
    while(bfs())
	{
        for(int i=1;i<=n;i++)
            cur[i]=head[i]; 
        while(flow=dfs(s,1<<29)) maxn+=flow;
    }
    printf("%lld",maxn);
    return 0;
}

如果将tot的初始值去掉(即去掉第15行中的=1)则会得到37分的好成绩

为什么?

2022/6/28 22:04
加载中...