mygr @ 2023-07-02 21:02:50
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,nums[505],from[505],x,y,z,Min=0x7fffffff,Map[505][505],Rank[505][505];
vector<int> p[505];//to egde
bool vis[505],can;
long long int ans;
queue<int> into;
int bfs()
{
into.push(s);
vis[s]=true;
while(!into.empty())
{
int now=into.front();
if(now==t)
{
while(!into.empty())
{
into.pop();
}
for(int i=1;i<=n;i++)
vis[i]=false;
can=true;
break;
}
into.pop();
for(int i=0;i<nums[now];i++)
{
if(Map[now][p[now][i]]<=0)
continue;
int to=p[now][i];
if(vis[to])
continue;
into.push(to);
vis[to]=true;
from[to]=now;
}
//cout<<"a";
}
}
int update()
{
int now=t,Min=0x7fffffff;
while(now!=s)
{
Min=min(Min,Map[from[now]][now]);
now=from[now];
}
now=t;
ans+=Min;
while(now!=s)
{
Map[now][from[now]]+=Min;
Map[from[now]][now]-=Min;
now=from[now];
}
}
int main()
{
//freopen("P3376_1.in","r",stdin);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
p[x].push_back(y);
p[y].push_back(x);
Map[x][y]=z;
nums[x]++;
nums[y]++;
}
can=true;
while(can)
{
can=false;
bfs();
update();
}
cout<<ans;
}
by P7GAB @ 2023-09-16 11:03:22
初步观察:数组太小,bfs、update没有返回值。