decoqwq @ 2018-07-07 18:50:50
qwq萌新只有80请求各位dalao指点
#include <bits/stdc++.h>
using namespace std;
int head[10010],dis[10010];
struct edge
{
int next,to,v;
}e[200010];
int n,m,s,t,cnt,ans=0;
queue<int> q;
void add(int u,int v,int dis)
{
cnt++;
e[cnt].to=v;
e[cnt].next=head[u];
e[cnt].v=dis;
head[u]=cnt;
}
int bfs()
{
memset(dis,-1,sizeof(dis));
while(!q.empty())
{
q.pop();
}
dis[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
if(dis[v]==-1&&e[i].v>0)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return dis[t]!=-1;
}
int dfs(int u,int exp)
{
if(u==t||!exp)
{
return exp;
}
int flow=0,tmp;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
if((dis[v]==dis[u]+1)&&e[i].v>0)
{
tmp=dfs(v,min(exp,e[i].v));
if(!tmp)
{
continue;
}
flow+=tmp;
exp-=tmp;
e[i].v-=tmp;
e[i^1].v+=tmp;
if(!exp)
{
break;
}
}
}
return flow;
}
int main()
{
memset(head,-1,sizeof(head));
memset(dis,-1,sizeof(dis));
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,z,0);
}
while(bfs())
{
ans+=dfs(s,0x3f3f3f3f);
}
cout<<ans;
return 0;
}
by AThousandSuns @ 2018-07-07 18:55:02
@刘浩宇(寂) 先%极fake的团长一发
你的cnt要初始化为-1或1,否则i^1就不是i的反向边
by decoqwq @ 2018-07-07 18:56:58
@AThousandSuns qaq cnt=1或-1都只有70分了qaq
by AThousandSuns @ 2018-07-07 18:59:13
@刘浩宇(寂) 话说加边的地方……
add(y,z,0); //hhh
by AThousandSuns @ 2018-07-07 18:59:41
@刘浩宇(寂) 反正cnt必须是奇数,不然就会GG
by decoqwq @ 2018-07-07 19:04:14
@AThousandSuns 好吧qwq谢谢
by decoqwq @ 2018-07-07 19:04:34
@AThousandSuns 加边怎么了qwq
by decoqwq @ 2018-07-07 19:07:32
@AThousandSuns 太感谢啦qwq
by AThousandSuns @ 2018-07-07 19:07:35
@刘浩宇(寂)
add(y,z,0) //add(y,x,0)?
by decoqwq @ 2018-07-07 19:08:27
@AThousandSuns 已经AC啦谢谢qwq,话说加错了还有80(雾)
by 狸狸养的敏敏 @ 2018-07-13 14:16:33
刚学OI做网络流%%%