nothing__ @ 2022-07-15 09:46:26
#include<iostream>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct edge{int x, y, c, pre, other;}a[41000];int alen, last[21000], h[21000], st, ed;
void ins(int x, int y, int c)
{
a[++alen]=edge{x, y, c, last[x], alen+1};last[x]=alen;
a[++alen]=edge{y, x, 0, last[y], alen-1};last[y]=alen;
}
bool bh()
{
memset(h, 0, sizeof(h)); h[st]=1;
queue<int>q;q.push(st);
while(!q.empty())
{
int x=q.front();
for(int k=last[x];k>0;k=a[k].pre)
{
int y=a[k].y;
if(h[y]==0&&a[k].c>0)
{
h[y]=h[x]+1;
q.push(y);
}
}
q.pop();
}
return h[ed]>0;
}
int findflow(int x, int f)
{
if(x==ed) return f;
int sx=0;
for(int k=last[x];k>0;k=a[k].pre)
{
int y=a[k].y;
if(a[k].c>0&&sx<f&&h[y]==(h[x]+1))
{
int sy=findflow(y, min(a[k].c, f-sx));
a[k].c-=sy; a[a[k].other].c+=sy;
sx+=sy;
}
}
if(sx==0) h[x]=0;
return sx;
}
int main()
{
int n, m;
scanf("%d%d%d%d", &n, &m, &st, &ed);
alen=0;memset(last, 0, sizeof(last));
for(int i=1;i<=m;i++)
{
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
ins(x, y, c);
}
long long s=0;
while(bh())
{
s+=findflow(st, 0x15f);
}
printf("%d\n", s);
return 0;
}
by nothing__ @ 2022-07-15 09:52:31
我们老师教的
by nothing__ @ 2022-07-15 09:53:50
他pop的是x吧?好像
by nothing__ @ 2022-07-15 09:54:58
@AFewSuns