Custlo0793 @ 2020-11-11 15:48:28
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#define min(a,b) a<b?a:b
#define N 10101
#define ll long long
#define inf 0x7fffffffffffffffll
using namespace std;
inline int read()
{
int x=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
int n,m,top=1,head[N],s,t,cur[N];
struct Node{
int v;
ll val;
int next;
}node[200100];
inline void addedge(int u,int v,ll val)
{
node[++top].v=v;
node[top].val=val;
node[top].next=head[u];
head[u]=top;
}
int vis[N],dep[N];
bool bfs(int s,int t)
{
memset(dep,0x3f,sizeof(dep));
memset(vis,0,sizeof(vis));
dep[s]=0;
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(dep[d]>dep[u]+1&&node[i].val){
dep[d]=dep[u]+1;
q.push(d);
if(d==t) return 1;
}
}
}
if(dep[t]!=0x3f3f3f3f)return 1;
return 0;
}
int dfs(int u,ll flow)
{
ll rlow=0,res=0,restflow=flow;
if(u==t || flow==0) return flow;
for(int i=cur[u];i!=-1;i=node[i].next)
{
cur[u]=i;
if(flow<=0) break;
int d=node[i].v;
if(node[i].val&&dep[d]==dep[u]+1)
{
rlow=dfs(d,min(restflow,node[i].val));
if(rlow)
{
node[i].val-=rlow;
node[i^1].val+=rlow;
res+=rlow;
restflow-=rlow;
if(!restflow) break;
}
}
}
return res;
}
int dinic(int s,int t)
{
int res=0;
while(bfs(s,t))
{
for(int i=1;i<=n;i++)cur[i]=head[i];
res+=dfs(s,inf);
}
return res;
}
int main()
{
memset(head,-1,sizeof(head));
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int u,v;
ll val;
u=read();
v=read();
val=read();
addedge(u,v,val);
addedge(v,u,0);
}
cout<<dinic(s,t);
return 0;
}
RT
by Custlo0793 @ 2020-11-11 15:49:33
求助!
by 幻影星坚强 @ 2020-11-11 15:50:22
res不该是long long吗
by Custlo0793 @ 2020-11-11 15:52:41
@幻影星坚强 大佬,写了long long还是WA
by 幻影星坚强 @ 2020-11-11 16:07:25
dinic函数不也应该是long long吗()
by 幻影星坚强 @ 2020-11-11 16:12:35
dfs也应该是long long()
by hater @ 2020-11-11 16:12:40
@Knuth_Morris_Pratt 好好看看还有哪里没有开ll
by Zxc200611 @ 2020-11-11 16:13:59
试试这个:
#define int long long
signed main()
...
by Zxc200611 @ 2020-11-11 16:14:24
@Knuth_Morris_Pratt
by Custlo0793 @ 2020-11-12 13:01:09
@Zxc200611 @hater @幻影星坚强 谢谢!!
--------------------此贴终结-------------------------------------------------------------------------------------------------------