Lacrymabre @ 2019-10-30 16:57:06
RT,背的板子相似勿喷谢谢
一下是萌新代码,TLE 2,9,10求助
#include<bits/stdc++.h>
#define N 100001
using namespace std;
int from[N],cnt;
int net[N],to[N],v[N];
int n,m,x,y,z;
int ans,flow;
int dis[N];
queue <int> q;
int S,T;
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
inline void add(int x,int y,int z)
{
net[cnt]=from[x];
to[cnt]=y;
v[cnt]=z;
from[x]=cnt++;
}
bool bfs()
{
memset(dis,0,sizeof(dis));dis[S]=0;
q.push(S);
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int i=from[cur];i!=-1;i=net[i])
{
int X=to[i];
if(dis[X]==-1&&v[i]>0)
{
dis[X]=dis[cur]+1;
q.push(X);
}
}
}
return dis[T]!=-1;
}
int dfs(int F,int exp)
{
if(F==T) return exp;
int flow=0,tmp=0;
for(int i=from[F];i!=-1;i=net[i])
{
int X=to[i];
if(dis[X]==dis[F]+1&&v[i]>0)
{
tmp=dfs(X,min(exp,v[i]));
if(!tmp) continue;
exp-=tmp;flow+=tmp;
v[i]-=tmp;
v[i^1]+=tmp;
if(!exp) break;
}
}
return flow;
}
int main()
{
memset(from,-1,sizeof(from));
n=read();m=read();S=read();T=read();
for(int i=1;i<=m;i++)
{
x=read();y=read();z=read();
add(x,y,z);add(y,x,0);
}
while(bfs()) ans+=dfs(S,0x7fffffff);
cout<<ans;
return 0;
}
by 乙津梦 @ 2019-10-30 17:38:12
@爆零_自动机 用vector存边,网络流会快很多
by xukuan @ 2019-10-30 17:40:43
@秦岭秋风 当前弧不加的话这题也是可做的
by saxiy @ 2019-10-31 17:24:24
HLPP不香嘛。。