osfly @ 2022-06-28 22:04:23
在这份代码中
#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分的好成绩
为什么?
by Smile_Cindy @ 2022-06-28 22:06:03
@osfly
如果tot不是从一开始的
那么i^1
就不是i
的反向边的编号
by 我是人999 @ 2022-06-28 22:21:10
楼上正解,补充几句:对于奇数
by Leonid @ 2022-07-09 08:15:55
@osfly 感谢。
by Anyakwi @ 2022-09-12 07:37:31
感谢