华容 @ 2019-06-23 16:03:24
求大佬看看为什么过不了#5
#include<bits/stdc++.h>
using namespace std;
int head[1000001],to[1000001],w[1000001],next[1000001],increase,deth[1000001],h[1000001],INT=0xffffff7;
int num=1,S,M,N,T,an,id;
queue <int> q;
void add(int a,int b,int c)
{
next[++num]=head[a];
head[a]=num;
to[num]=b;
w[num]=c;
}
int main()
{
ifstream fin("123.in");
int s,e,c,j,k;
int ui,vi,wi;//ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)
int i;
fin>>N>>M>>S>>T;//分别表示点的个数、有向边的个数、源点序号、汇点序号.
for(i=1;i<=M;i++)
{
fin>>ui>>vi>>wi;
add(ui,vi,wi);
add(vi,ui,0);
}
while(1)
{
while(!q.empty())
{
q.pop();
}
memset(h,0,sizeof (h));
memset(deth,0,sizeof(deth));
q.push(S);
deth[S]=INT;
while(!q.empty())
{
s=q.front();
q.pop();
if(s==T)
{
break;
}
for(e=head[s];e!=0;e=next[e])
{
c=to[e];
if(h[c]==0&&w[e]>0)
{
h[c]=s;
q.push(c);
deth[c]=min(w[e],deth[s]);
}
}
}
if(h[T]==0)
{
break;
}
j=T;
while(j!=S)
{
for(k=head[j];k!=0;k=next[k])
{
if(to[k]==h[j])
{
w[k]+=deth[T];
w[1^k]-=deth[T];
break;
}
}
j=h[j];
}
an=an+deth[T];
}
cout<<an;
}