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 传奇666666 @ 2019-10-30 16:59:11
大哥,你不觉得开反向边就需要两倍的边数了吗?还只开一倍的空间。
by Lacrymabre @ 2019-10-30 16:59:42
@传奇666666 !我试试
by Lacrymabre @ 2019-10-30 17:01:03
@传奇666666 现在全部TLE了
by Lacrymabre @ 2019-10-30 17:01:11
继续求助
by 乙津梦 @ 2019-10-30 17:07:07
用vector啊
by Uniecho1 @ 2019-10-30 17:08:22
@爆零_自动机 不加当前弧优化时间复杂度是假的...
by Lacrymabre @ 2019-10-30 17:09:08
@缘生艺转 不会awa
by Lacrymabre @ 2019-10-30 17:09:24
@秦岭秋风 也就是说要加优化???
by CreeperLordVader @ 2019-10-30 17:09:57
@爆零_自动机 可能是队列没清空吧
队列最好开在函数里
by Uniecho1 @ 2019-10-30 17:11:44
@爆零_自动机 嗯是的(虽然我都是好久以前做的这个题了)