网络流模板 注释详细

注释详细"/>

网络流模板 注释详细

该写的都在注释里了，详阅

放俩B站视频

【算法讲堂】【电子科技大学】【ACM】网络流入门

网络流算法—Min Cost Flow 最小费用流问题详解

网络流重点在建模，在构图，算法只是模板，要刷题，就像dp

模板注释比较详细了，不懂的看视频，Dinic代码第四行还有一篇解析的链接

求解最大流 Dinic

#include <iostream>//dinic
#include <cstdio>//时间复杂度上界是M*N^2 但实际上Dinic算法比这个理论上界好得多。有的题甚至能跑一千万点 而N^3最多跑400点 
#include <queue>//如果所有边容量均为1，那么时间复杂度是O(min(N^0.67,M^0.5) * M) 对于二分图最大匹配这样的特殊图，时间复杂度是O(N^0.5 * M)
#include <cstring>//.html是解析 
#define mem(a,b) memset(a,b,sizeof(a))
const int M=1e6+10,N=1e3+10,INF=0x3f3f3f3f;
using namespace std;
int m;//n为节点数，m为边数
int s,e;//s是起点，e是终点
struct node { //链式前向星int to,next,w;
} edge[M];
int head[N],cnt;
int vis[N];//节点层数
void addedge(int from,int to,int w) {edge[cnt].to=to;edgecnt].next=head[from];edge[cnt].w=w;head[from]=cnt++;
} 
int bfs() {//建立层次网络，每次时间复杂度M，最多建立N个，所以总复杂度上限NM //每次都要重新分层mem(vis,0);queue<int> que;vis[s]=1;//层数que.push(s);while(que.size()) {int u=que.front();que.pop();for(int i=head[u]; ~i; i=edge[i].next) {int to=edge[i].to;//如果当前流的水流值已经为0 或者 vis[to]层数划分不符合要求if(edge[i].w==0||vis[to]) continue;//不能写vis[to]!=vis[to]+1,vis[to]初始值全是0 应该写如果to没有被访问过(否则它的层数>0)que.push(to);vis[to]=vis[u]+1;}}return vis[e];//如果汇点不在层次网络中,即不存在增广路,则返回0,算法结束 
}
int dfs(int u,int flow) { //到达终点或者当前流的值为0返回if(u==e||flow==0) return flow;for(int i=head[u]; ~i; i=edge[i].next) {head[u] = i;//当前弧优化 因为for循环的i更新的条件是w==0或w!=0但k==0,而k==0就意味着（45行）flow==0，总之这条路废了i才会更新，既然废了，那就把头结点换成新的i，以免再走一次废路浪费时间 int to=edge[i].to;int w=edge[i].w;//不符合增广路径的要求 或者 当前流的值为0if(vis[to]!=vis[u]+1||w==0) continue;//继续按照当前增广路径搜索。int k=dfs(to,min(flow,w));//下一波水流是管道容纳量和当前水流的最小值if(k>0) {//对边的只进行修改，同时保留回退的空间。edge[i].w-=k;edge[i^1].w+=k;//i^1是反边，用来反悔，这是我们建边的时候故意设置的return k;//0^1=1，2^1=3，也就是0反边是1，2反边是3，所以我们建立正向边是0,2,4,8，...，2k，反边是正边+1  0(+) 1(-) 2(+) 3(-)…… }}return 0;
}
void dinic() {int ans=0,k=0;//bfs()分层找处增广路径while(bfs()) { //终点e层数为0说明汇点不在层次网络中，算法结束 要么一开始路就不通，要么路被流完了 //找出每条增广路径的最小流while((k=dfs(s,INF))>0) //初始水流设为无穷大//所有增广路径的最小流的和即是最大流ans+=k;}printf("%d",ans);
}
void init() {mem(head,-1);cnt=0;
}
int main() {init();scanf("%d%d%d",&m,&s,&e);for(int i=1;i<=m;i++){int a,b,v;scanf("%d%d%d",&a,&b,&v);addedge(a,b,v); addedge(b,a,0);//反向边 } dinic();return 0;
}
/*
例 
6 1 5
1 2 4
1 3 6
2 3 2
2 4 3
3 5 4
4 5 5
*/

求解最大流最小费用流 SPFA

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
const int N=5e3+50,INF=0x3f3f3f3f;
using namespace std;
bool vis[N];
int n, m, s, t;//节点数、边数、源点、汇点 
int u, v, c, w;//每条边的起点、终点、容量、费用 
int cost[N], pre[N], last[N], flow[N];//源点到该点的花费，该点的前驱，前驱的地址(cnt) ， 限制该点增广路径的流
int maxFlow, minCost;//最大流，最小花费 
struct Edge {//链式前向星，不过next变成from，由从后向前遍历改为从前向后遍历 cnt要初始化为-1 int from, to, flow, cost;
} edge[N];
int head[N], cnt;
queue <int> q;
//最大流最小费用流
void addedge(int from, int to, int flow, int cost) { //建正边和反边edge[++cnt].from = head[from];//正边edge[cnt].to = to;edge[cnt].flow = flow;edge[cnt].cost = cost;head[from] = cnt;edge[++cnt].from = head[to];//反边edge[cnt].to = from;edge[cnt].flow = 0;edge[cnt].cost = -cost;head[to] = cnt;
}
bool SPFA(int s, int t) {memset(cost, 0x3f, sizeof(cost));memset(flow, 0x3f, sizeof(flow));memset(vis, 0, sizeof(vis));q.push(s);vis[s] = 1;cost[s] = 0;pre[t] = -1;while (!q.empty()) {int now = q.front();q.pop();vis[now] = 0;for (int i = head[now]; ~i; i = edge[i].from) {//如果流大于0说明这条边还有用的价值if (edge[i].flow>0 && cost[edge[i].to]>cost[now] + edge[i].cost) {cost[edge[i].to] = cost[now] + edge[i].cost;//记录最短路径，找出花费最小的增广路径//记录当前节点的上一个节点pre[edge[i].to] = now;//上一条边的地址last[edge[i].to] = i;//记录限制当前增广路径的流flow[edge[i].to] = min(flow[now], edge[i].flow);//最短路径算法if (!vis[edge[i].to]) {vis[edge[i].to] = 1;q.push(edge[i].to);}}}}return pre[t] != -1;
}
void MCMF() {//min cost max flow最大流最小花费 //SPFA(s,t)找出s->t的增广路径while (SPFA(s, t)) {int now = t;//记录最大流的大小maxFlow += flow[t];//记录当前增广路径的花费minCost += flow[t] * cost[t];while (now != s) {//对路径进行反向建边，方便回退//last[now]   now的上一条边的位置edge[last[now]].flow -= flow[t];edge[last[now] ^ 1].flow += flow[t];//反边 //now的父节点now = pre[now];}}
}
//spfa + dinic
int main() {ios::sync_with_stdio(false);cin.tie(0);memset(head, -1, sizeof(head));memset(pre,0,sizeof(pre));cnt = -1;//初始化cout << "节点数为：";cin >> n;cout << "边数为：";cin >> m;cout << "源点编号为：";cin >> s;cout << "汇点编号为：";cin >> t;cout << "输入 " << m << " 条边的信息：" << endl;while (m--) {cout << "起点：";cin >> u;cout << "终点：";cin >> v;cout << "容量：";cin >> c;cout << "费用：";cin >> w;cout << "-----------------" << endl;addedge(u, v, c, w);}MCMF();cout << "最大流为：" << maxFlow << endl;cout << "最小费用为：" << minCost << endl;cout << endl;system("pause");return 0;
}