1.最大流

由源点$s$到汇点$t$的最大流量。
图的最大流$\le$将图进行割边的流量(任意割)

证明最大流等于最小割:

简略版)
对于一张图网络，假设开始是一个连通图且源点$s$和汇点$t$都在一个集合里，设图网络的最大流为$F$，那么$F$等于从源点$s$流出的流量(假设源点有无限的流量)且$F$等于从汇点$t$流入的流量，当对连通图进行割边后集合会被分成两个集合，源点与汇点分别在两个集合中，此时源点流出的流量等于汇点流入的流量等于割边的流量。即图网络的最大流等于最小割。

思想

发现每次从$s$到$t$进行对残量网络的一条路径减去路径的最小值，当沿残量网络无法到达$t$时，即构造出了割边。复杂度为 O ( n 2 m ) O(n^2m) O(n2m)，但实际远远达到不了这里。

代码

#include 
using namespace std;
using ll = long long ;
const int N = 5e3+10 ;
ll e[N<<1],ne[N<<1],w[N<<1],h[N<<1],k;
void add(int a,int b,int c){e[++k]=b,ne[k]=h[a],w[k]=c,h[a]=k;
}
ll dep[N];
bool bfs(int s,int t){memset(dep,0,sizeof dep);dep[s]=1;queue<int>q;q.push(s);while(!q.empty()){int t=q.front();q.pop();for(int i=h[t];i;i=ne[i]){int j=e[i];if(w[i] and !dep[j]){dep[j]=dep[t]+1;q.push(j);}}}return dep[t];
}
ll dfs(int s,int t,ll in){if(s==t)return in;ll out=0;for(int i=h[s];i;i=ne[i]){int j=e[i];if(w[i] and dep[j]==dep[s]+1){ll x=dfs(j,t,min(in,w[i]));w[i]-=x;w[i^1]+=x;out+=x;in-=x;}}if(out==0)dep[s]=0;return out;
}
ll dinic(int s,int t){ll ans=0;while(bfs(s,t))ans+=dfs(s,t,1e18);return ans;
}
template<class Tp=int>
Tp read(){char ch=getchar();bool f=1;Tp x=0;while(!isdigit(ch)){if(ch=='-')f=false;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return f?x:-x;
}
template<class Tp=int>
void print(Tp n){if(n>9)print(n/10);putchar(n%10|'0');
}
int main()
{k=1;ios::sync_with_stdio(false);int n,m,s,t;n=read(),m=read(),s=read(),t=read();for(int i=0,a,b,c;i<m;i++){a=read(),b=read(),c=read();add(a,b,c);add(b,a,0);}print<ll>(dinic(s,t));
}

2.最小费用最大流

很明显是在最小费用的基础上求最大流。

思想

每次使用dijskra或spfa以单位费用最小找到从$s$到$t$的最小费用路径，和构造最大流一样构造割边即可，复杂度为 O ( m n l o g 2 n ) O(mnlog_2n) O(mnlog2​n) O ( n 2 m ) O(n^2m) O(n2m)

代码

#include 
using namespace std;
using ll = long long ;
const int N = 5e4+10 ;
const ll inf = 1e10 ;
ll e[N<<1],ne[N<<1],h[N<<1],w[N<<1],c[N<<1];
int k=1;
void add(int a,int b,int c,int d){e[++k]=b,ne[k]=h[a],h[a]=k;w[k]=c,::c[k]=d;
}
ll dis[N];
bool vis[N];
int dep[N];
ll flow[N];
int pre[N],last[N];
bool spfa(int s,int t){memset(dis,0x7f,sizeof dis);memset(flow,0x7f,sizeof flow);memset(pre,-1,sizeof pre);memset(vis,0,sizeof vis);queue<int>q;q.push(s);pre[s]=0;vis[s]=true;dis[s]=0;while(!q.empty()){int t=q.front();q.pop();vis[t]=false;for(int i=h[t];i;i=ne[i]){int j=e[i];if(w[i]&&dis[j]>dis[t]+c[i]){last[j]=i;dis[j]=dis[t]+c[i];pre[j]=t;flow[j]=min(flow[t],w[i]);if(!vis[j]){q.push(j);vis[j]=true;}}}}return pre[t]!=-1;
}
void dinic(int s,int t){ll F=0,D=0;while(spfa(s,t)){int x=t;F+=flow[t];D+=flow[t]*dis[t];while(x!=s){w[last[x]]-=flow[t];w[last[x]^1]+=flow[t];x=pre[x];}}cout<<F<<" "<<D;
}
int main()
{ios::sync_with_stdio(false);int n,m,s,t;cin>>n>>m>>s>>t;for(int i=0,u,v,w,c;i<m;i++){cin>>u>>v>>w>>c;add(u,v,w,c);add(v,u,0,-c);}dinic(s,t);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！