社区讨论
为什么tot的值从1改成0就会炸
P3376【模板】网络最大流参与者 4已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo127xfz
- 此快照首次捕获于
- 2023/10/22 14:00 2 年前
- 此快照最后确认于
- 2023/11/02 13:29 2 年前
CPP
#include<bits/stdc++.h>
#define int long long
#define inf 2147483647
using namespace std;
struct node{
int nxt;
int to;
int val;
}e[10010];
int tot=0,now[210],head[210],dis[210];
int n,m,s,t;
void add(int u,int v,int val)
{
e[++tot].to=v;
e[tot].val=val;
e[tot].nxt=head[u];
head[u]=tot;
e[++tot].to=u;
e[tot].val=0;
e[tot].nxt=head[v];
head[v]=tot;
}
/*inline void add(int u,int v,long long w) {
e[++tot].to=v;
e[tot].val=w;
e[tot].nxt=head[u];
head[u]=tot;
e[++tot].to=u;
e[tot].val=0;
e[tot].nxt=head[v];
head[v]=tot;
}*/
int bfs()
{
for(int i=1;i<=n;i++)dis[i]=inf;
queue<int > q;
q.push(s);
dis[s]=0;
now[s]=head[s];
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].val>0&&dis[v]==inf)
{
q.push(v);
dis[v]=dis[x]+1;
now[v]=head[v];
if(v==t)return 1;
}
}
}
return 0;
}
int dfs(int x,int sum)
{
if(x==t)return sum;
int k,res=0;
for(int i=now[x];i&∑i=e[i].nxt)
{
now[x]=i;
int v=e[i].to;
if(e[i].val>0&&(dis[v]==dis[x]+1)) {
k=dfs(v,min(sum,e[i].val));
if(k==0) dis[v]=inf;
e[i].val-=k;
e[i^1].val+=k;
res+=k;
sum-=k;
}
}
return res;
}
int ans=0;
signed main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int u,v,e;
cin>>u>>v>>e;
add(u,v,e);
}
while(bfs())
{
ans+=dfs(s,inf);
}
cout<<ans;
return 0;
}
++tot不应该是先加再计算吗,那e[1]不是会空出来吗
回复
共 3 条回复,欢迎继续交流。
正在加载回复...