\[\texttt{updated on 2021.10.31:} \] \[\texttt{我透 刚才都没发现我SSP的当前弧优化加到狗身上去了(((} \] \[\texttt{加了快150ms} \]
1.最大流
分为复杂度\(O(nm^2)\)的EK和\(O(n^2m)\)的Dinic.
EK最大流模板:
//this code can get 81 points in P3381,which is a template problem.
#include <bits/stdc++.h>
#define int long long
#define MAXN 2000001
#define INF 1e8+10
using namespace std;
inline int r()
{
int fed=0;
bool flag=1;
char in=getchar();
while(!isdigit(in))
flag&=(in!='-'),in=getchar();
while(isdigit(in))
fed=fed*10+in-'0',in=getchar();
return (2*flag-1)*fed;
}
int n,m,s,t;
int ans;
int head[MAXN],cntr;
int A[MAXN],path[MAXN];
struct edge{
int u,v,next,flow;
}e[MAXN];
inline void add(int u,int v,int flow)
{
e[cntr].u=u;
e[cntr].v=v;
e[cntr].flow=flow;
e[cntr].next=head[u];
head[u]=cntr++;
}
inline void orz(int u,int v,int flow)
{
add(u,v,flow);
add(v,u,0);
}
inline void EK()
{
while(true)
{
memset(A,0,sizeof(A));
queue<int> q;
q.push(s);
A[s]=INF;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(!A[v]&&e[i].flow)
{
path[v]=i;
A[v]=min(A[u],e[i].flow);
q.push(v);
}
}
if(A[t])
break;
}
if(!A[t])
break;
for(int i=t;i!=s;i=e[path[i]].u)
{
e[path[i]].flow-=A[t];
e[path[i]^1].flow+=A[t];
}
ans+=A[t];
}
}
signed main()
{
memset(head,-1,sizeof(head));
n=r(),m=r();
s=r(),t=r();
for(int i=1;i<=m;i++)
{
int u,v,w;
u=r(),v=r();
w=r();
orz(u,v,w);
}
EK();
printf("%lld",ans);
return 0;
}
Dinic最大流模板:
//100 points in P3381.
#include <bits/stdc++.h>
#define ri register int
#define int long long
#define MAXN 1000001
using namespace std;
const int INF=0x7fffffff;
int n,m,s,t;
int depth[MAXN],head[MAXN],cur[MAXN],cntr;
//queue<int> q;
struct node{
int to,next,flow;
}e[MAXN<<2];
inline void add(int u,int v,int flow)
{
e[cntr].to=v;
e[cntr].flow=flow;
e[cntr].next=head[u];
head[u]=cntr++;
}
inline void orz(int u,int v,int flow)
{
add(u,v,flow);
add(v,u,0);
}
inline int r()
{
int fed=0;
char i=getchar();
bool flag=1;
while(!isdigit(i))
flag&=(i!='-'),i=getchar();
while(isdigit(i))
fed=fed*10+i-'0',i=getchar();
return (2*flag-1)*fed;
}
int q[MAXN];
inline bool bfs()
{
memset(depth,-1,sizeof(depth));
depth[s]=1;
cur[s]=head[s];
int l=0,r=1;
q[++l]=s;
while(l<=r)
{
int u=q[l++];
for(ri i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if(depth[v]==-1&&e[i].flow)
{
depth[v]=depth[u]+1;
q[++r]=v;
cur[v]=head[v];
if(v==t)
return true;
}
}
}
return 0;
}
inline int dfs(int now,int fl)
{
if(now==t||fl==0)
return fl;
int tflow=0;
for(ri i=cur[now];~i&&tflow<fl;i=e[i].next)
{
cur[now]=i;
int v=e[i].to;
if(depth[v]==depth[now]+1&&e[i].flow)
{
int cf=dfs(v,min(e[i].flow,fl-tflow));
if(!cf)
depth[v]=-1;
e[i].flow-=cf;
e[i^1].flow+=cf;
tflow+=cf;
}
}
return tflow;
}
inline void Dinic()
{
int res=0,ad=0;
while(bfs())
{
while(ad=dfs(s,INF))
res+=ad;
}
printf("%lld",res);
}
signed main()
{
n=r(),m=r();
s=r(),t=r();
memset(head,-1,sizeof(head));
for(ri i=1;i<=m;i++)
{
int u,v,w;
u=r(),v=r();w=r();
orz(u,v,w);
}
Dinic();
return 0;
}
2.最小费用最大流
目前只会写SSP算法，用SPFA替代Dinic里的bfs来求最少花费的增广路.
SSP模板:
#include <bits/stdc++.h>
#define MAXN 50005
#define ri register int
using namespace std;
const int INF=0x3f3f3f3f;
inline int r()
{
int fed=0;
char in=getchar();
bool flag=1;
while(!isdigit(in))
flag&=(in!='-'),in=getchar();
while(isdigit(in))
fed=fed*10+in-'0',in=getchar();
return (2*flag-1)*fed;
}
int n,m,s,t,cntr,head[MAXN];
int ans,res;
int dist[MAXN];
bool vis[MAXN];
int q[MAXN<<2];
int cur[MAXN];
struct node{
int to,next,flow,cost;
}e[MAXN<<2];
inline void add(int u,int v,int w,int c)
{
e[cntr].to=v;
e[cntr].flow=w;
e[cntr].cost=c;
e[cntr].next=head[u];
head[u]=cntr++;
}
inline void orz(int u,int v,int w,int c)
{
add(u,v,w,c);
add(v,u,0,-c);
}
inline bool SPFA()
{
//已死
//算法
//重现
//光辉
//(↑)
memset(dist,0x3f,sizeof(dist));
memcpy(cur,head,sizeof(head));
int l=0,r=1;
q[++l]=s,dist[s]=0;
vis[s]=1;
while(l<=r)
{
int u=q[l++];
vis[u]=0;
for(ri i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if(e[i].flow&&dist[v]>dist[u]+e[i].cost)
{
dist[v]=dist[u]+e[i].cost;
if(!vis[v])
vis[v]=1,q[++r]=v;
}
}
}
return dist[t]!=INF;
}
inline int dfs(int now,int maxfl)
{
if(now==t||maxfl==0)
return maxfl;
vis[now]=1;
int cytti=0;
for(ri i=cur[now];~i&&cytti<maxfl;i=e[i].next)
{
cur[now]=i;
int v=e[i].to;
if(!vis[v]&&e[i].flow&&dist[v]==dist[now]+e[i].cost)
{
int cf=dfs(v,min(e[i].flow,maxfl-cytti));
if(cf)
{
ans+=cf*e[i].cost;
e[i].flow-=cf;
e[i^1].flow+=cf;
cytti+=cf;
}
}
}
vis[now]=0;
return cytti;
}
inline void Dinic()
{
int ad=0;
while(SPFA())
while(ad=dfs(s,INF))
res+=ad;
printf("%d %d",res,ans);
}
int main()
{
memset(head,-1,sizeof(head));
n=r(),m=r();
s=r(),t=r();
for(ri i=1;i<=m;i++)
{
int u,v,w,c;
u=r(),v=r();
w=r(),c=r();
orz(u,v,w,c);
}
Dinic();
return 0;
}
\[\color{skyblue}{\texttt{And We,}} \] \[\color{skyblue}{\texttt{We Burn Faster Than Lights,}} \] \[\color{skyblue}{\texttt{Shine Across In The Night Sky,}} \] \[\color{skyblue}{\texttt{We Burn Faster Than Lights.}} \] \[\color{gold}{◢_◤} \]