environmentalist @ 2021-11-05 19:23:29
样例八下载下来本地过了,在线IDE“输入长度不合法” ??
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
#define re register
#define in inline
using namespace std;
const ll inf=2147483647;
in ll read()
{
ll x=0,k=1;
char c=getchar();
while(!isdigit(c))
{
if(c=='-') k=-1;
c=getchar();
}
while(isdigit(c))
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*k;
}
ll z,ans;
int n,m,s,t;
int x,y;
struct eg{
int v,nxt;
ll w;
}edge[10001];
int head[5001],dis[5001],cnt=1,now[5001];
in void build(int u,int v,ll w)
{
edge[++cnt].v=v;
edge[cnt].w=w;
edge[cnt].nxt=head[u];
head[u]=cnt;
edge[++cnt].v=u;
edge[cnt].w=0;
edge[cnt].nxt=head[v];
head[v]=cnt;
}
in int bfs()
{
for(re int i=1;i<=n;++i)
{
dis[i]=inf;
}
queue<int> q;
q.push(s);
dis[s]=0;
now[s]=head[s];
while(!q.empty())
{
int u=q.front();
q.pop();
for(re int i=head[u];i!=0;i=edge[i].nxt)
{
int v=edge[i].v;
if(edge[i].w>0 and dis[v]==inf)
{
dis[v]=dis[u]+1;
q.push(v);
now[v]=head[v];
if(v==t) return 1;
}
}
}
return 0;
}
in ll dfs(int x,ll left)
{
if(x==t) return left;
ll k,out=0;
for(re int i=now[x];i!=0 and left!=0;i=edge[i].nxt)
{
int v=edge[i].v;
if(edge[i].w>0 and dis[v]==dis[x]+1)
{
k=dfs(v,min(left,edge[i].w));
if(k==0) dis[v]=inf;
left-=k,out+=k;
edge[i].w-=k,edge[i^1].w+=k;
}
}
return out;
}
in void dinic()
{
while(bfs())
{
ans+=dfs(s,inf);
}
}
int main()
{
n=read(),m=read(),s=read(),t=read();
for(re int i=1;i<=m;++i)
{
x=read(),y=read(),z=read();
build(x,y,z);
}
dinic();
printf("%lld",ans);
return 0;
}
by JoaoFelix @ 2021-11-05 19:42:04
特尔施特根!
by environmentalist @ 2021-11-11 20:40:34
?确实(这不是重点)