hwwqy @ 2023-10-16 11:46:04
#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]不是会空出来吗
by lzyqwq @ 2023-10-16 11:47:48
是要把e[1]空出来啊,这样 i
和 i^1
才是一对双向边
by hyj0824 @ 2023-10-16 12:02:49
因为你的链式前向星(链表)判断达到链表结尾时是 for(int i=head[x];i;i=e[i].nxt)
,是不能有编号为0的边的。除非你初始把head全赋值成 -1才行。
by Zikl @ 2023-10-16 22:16:30
e[i].val-=k;
e[i^1].val+=k;
因为上面这个东西,2^1=3,3^1=2。你的反向边就靠这个
by Kikcer @ 2023-11-28 20:31:59
感谢,找半天错看到你这个才知道错哪了