@[楚泫](/space/show?uid=107960) EK和Dinic求的东西是一样的，只不过EK的效率没Dinic高
by RiverFun @ 2019-03-12 14:37:32
大佬能帮忙瞅一眼这份只能过样例的代码嘛x
@[Steve_braveman](/space/show?uid=96570)
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define space putchar(' ')
#define endl putchar('\n')
#define debug puts("------------------------")
#define F(i,x,n) for(int i=x;i<=n;++i)
#define F_(i,x,n) for(int i=x;i>=n;--i)
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
inline int Rem() {int a=0,c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();return a*=b; }
inline void write(int x) {if(x>9)write(x/10);putchar('0'+x%10);}
inline void W(int x) {if(x<0){putchar('-'),x=-x;}write(x);}
/**/
const int N=1e5+5,inf=0x3f3f3f3f;
int n,s,t,head[N],cnt=1,out[N];
bool vis[N];
struct edge
{
int nxt,to,c;
}e[N<<1];
struct PRE
{
int from,edge;
}pre[N];
/**/
inline void add(int u,int v,int c)
{
e[++cnt]=(edge){head[u],v,c};
head[u]=cnt;
}
int bfs()
{
memset(vis,0,sizeof(vis));
memset(pre,0,sizeof(pre));
queue<int>q;
vis[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].c&&!vis[v])
{
vis[v]=1;
pre[v].from=u;
pre[v].edge=i;
if(v==t) return 1;
q.push(v);
}
}
}
return 0;
}
void EK()
{
int maxflow=0;
while(bfs())
{
int mi=0x3f3f3f3f;
for(int i=t;i!=s;i=pre[i].from)
{
mi=min(mi,e[pre[i].edge].c);
}
for(int i=t;i!=s;i=pre[i].from)
{
e[pre[i].edge].c-=mi;
e[pre[i].edge^1].c+=mi;
}
maxflow+=mi;
}
cout<<maxflow<<'\n';
}
int main()
{
read(n);read(s);t=n+1;
for(int i=1,a,b,c;i<n;i++)
{
read(a);read(b);read(c);
add(a,b,c);
add(b,a,0);
out[a]++;
}
for(int i=1;i<=n;i++) if(!out[i]) add(i,t,0X7f7f7f7f),add(t,i,0);
EK();
}
```
by 楚泫 @ 2019-03-12 14:47:33
@[楚泫](/space/show?uid=107960) 题目中给的不是有向边
by djh123 @ 2019-03-12 15:04:43
@[楚泫](/space/show?uid=107960) dinic和EK的区别只是复杂度而已qwq
by ニヒル @ 2019-03-12 15:04:48
@[楚泫](/space/show?uid=107960)
```cpp
add(a,b,c);
add(b,a,0);
```
改为
```cpp
add(a,b,c);
add(b,a,c);
```
by RiverFun @ 2019-03-12 15:05:57
@[楚泫](/space/show?uid=107960) 2e5的边表可能不太够。不只有树上的边
by djh123 @ 2019-03-12 15:07:08
@[楚泫](/space/show?uid=107960)
```cpp
out[a]++;
```
改为
```cpp
out[a]++;
out[b]++;
```
by RiverFun @ 2019-03-12 15:08:07
```cpp
for(int i=1;i<=n;i++) if(!out[i]) add(i,t,0X7f7f7f7f),add(t,i,0);
```
改为
```cpp
for(int i=1;i<=n;i++) if(out[i] == 1) add(i,t,0X7f7f7f7f),add(t,i,0);
```
by RiverFun @ 2019-03-12 15:09:10
@[楚泫](/space/show?uid=107960) 楼上的楼上正解qwq，可以考虑按照dfs序建边
by ニヒル @ 2019-03-12 15:10:21
完了，打字速度太慢了……无视掉我吧
by ニヒル @ 2019-03-12 15:11:07