Tangent233 @ 2021-11-26 20:30:10
#include<bits/stdc++.h>
using namespace std;
const int maxn=210;
const long long inf=1e10+10;
int n,m,s,t;
struct edge
{
int from,to,cap,flow;
};
vector<edge> edges;
vector<int> g[maxn];
long long a[maxn],p[maxn];
void addedge(int f,int t,int c)
{
edges.push_back(edge{f,t,c,0});
edges.push_back(edge{t,f,0,0});
int m=edges.size();
g[f].push_back(m-2);
g[t].push_back(m-1);
}
unsigned int maxflow(int s,int t)
{
unsigned int flow=0;
while(1)
{
memset(a,0,sizeof(a));
queue<int> q;
q.push(s);
a[s]=inf;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<g[x].size();i++)
{
edge& e=edges[g[x][i]];
if(!a[e.to]&&e.cap>e.flow)
{
p[e.to]=g[x][i];
a[e.to]=min(a[x],(long long)e.cap-e.flow);
q.push(e.to);
}
}
if(a[t]) break;
}
if(!a[t]) break;
for(int u=t;u!=s;u=edges[p[u]].from)
{
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
flow+=a[t];
}
return flow;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main()
{/*
freopen("P3376.in","r",stdin);
freopen("P3376.ans","w",stdout);
*/ n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;i++)
{
int a,b,c;
a=read(),b=read(),c=read();
addedge(a,b,c);
}
cout<<maxflow(s,t)<<endl;
return 0;
}
怎么溢出了 贺了oiwiki的代码
by _Yoimiya_ @ 2021-11-27 11:32:35
你需要
#define int long long