概述
题目链接:P3376 【模板】网络最大流
这几天敲了几遍最大流的板子,还是有一些细节处理不好
在这里总结一下
- 前向星开边的数组的时候记得要开大一点,然后记得初始化head数组与tot
- dfs的时候应该是这篇文章下面贴的代码稍微快一点
- level数组的用途是判断层次,初始化的值可以灵活变化,不作要求
- tot的值一定要初始化为0
原因:
- 在dfs的时候我们要用到正向边减流,反向边加流,我们是用当前边的编号异或1去找与当前边反向的边的编号的
- 在tot值初始为0的情况下,拿建立的第一条边来说,他的编号是0,他的反向边编号为0+1 = 1,第二条边,编号为2,反向边编号为2+1 = 3……
- 偶数异或1相当于加1,奇数异或1相当于减一,这正好符合我们建边时候的顺序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 1e5;
struct node
{
int c;
int to;
int next;
} edge[N*10];
int n,m,tot;
int head[N];
int level[N];
void add(int u, int v, int w)
{
edge[tot].c = w;
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
edge[tot].c = 0;
edge[tot].to = u;
edge[tot].next = head[v];
head[v] = tot++;
}
int bfs(int s, int d)
{
for(int i = 0; i <= n; i++)
{
level[i] = -1;
}
level[s] = 0;
queue<int> q;
q.push(s);
while(q.size())
{
int u = q.front();
if(u == d) return 1;
q.pop();
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
int c = edge[i].c;
if(level[v] == -1 && c)
{
level[v] = level[u]+1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u, int d, int f)
{
if(u == d) return f;
int t = 0;
int tmp;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
int c = edge[i].c;
if(c && level[v] == level[u]+1 && (tmp = dfs(v, d, min(f, c))))
{
edge[i].c -= tmp;
edge[i^1].c += tmp;
t += tmp;
f -= tmp;
if(!f) break;
}
}
if(t) return t;
level[u] = -1;
return 0;
}
int Dinic(int s, int d)
{
int ans = 0;
while(bfs(s, d))
{
int tmp = dfs(s, d, inf);
if(!tmp) break;
ans += tmp;
}
return ans;
}
int main()
{
int s,d,u,v,w;
scanf("%d %d %d %d",&n,&m,&s,&d);
tot = 0;
for(int i = 0; i <= n; i++)
{
head[i] = -1;
}
while(m--)
{
scanf("%d %d %d",&u,&v,&w);
if(u == v) continue;
add(u, v, w);
}
printf("%dn",Dinic(s, d));
return 0;
}
最小费用最大流
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 500010;
struct node
{
int w,c;
int to;
int next;
} edge[N];
int n;
int pre[N];
int vis[N];
int dis[N];
int head[N],tot;
void add(int u, int v, int c, int w)
{
edge[tot].c = c;
edge[tot].w = w;
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
edge[tot].c = 0;
edge[tot].w = -w;
edge[tot].to = u;
edge[tot].next = head[v];
head[v] = tot++;
}
int spfa(int s, int d)
{
memset(pre, -1, sizeof(pre));
memset(vis, 0, sizeof(vis));
memset(dis, inf, sizeof(dis));
vis[s] = 1;
dis[s] = 0;
queue<int> q;
q.push(s);
while(q.size())
{
int u = q.front();
vis[u] = 0;
q.pop();
for(int i = head[u]; i != -1; i = edge[i].next)
{
if(edge[i].c)
{
int v = edge[i].to;
int w = edge[i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pre[v] = i;
if(!vis[v])
{
vis[v] = 1;
q.push(v);
}
}
}
}
}
return pre[d] != -1;
}
void mcmf(int s, int d)
{
int ans = 0;
int tot = 0;
while(spfa(s, d))
{
int tmp = inf;
for(int i = d; i != s; i = edge[pre[i]^1].to)
{
tmp = min(edge[pre[i]].c, tmp);
}
tot += tmp;
for(int i = d; i != s; i = edge[pre[i]^1].to)
{
edge[pre[i]].c -= tmp;
edge[pre[i]^1].c += tmp;
ans += edge[pre[i]].w*tmp;
}
}
printf("%d %dn",tot, ans);
}
int main()
{
int m,u,v,w,c,s,d;
tot = 0;
memset(head, -1, sizeof(head));
scanf("%d %d %d %d",&n,&m,&s,&d);
while(m--)
{
scanf("%d %d %d %d",&u,&v,&c,&w);
add(u, v, c, w);
}
mcmf(s, d);
return 0;
}
最后
以上就是英俊小霸王为你收集整理的【模板】网络最大流 + 最小费用最大流的全部内容,希望文章能够帮你解决【模板】网络最大流 + 最小费用最大流所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复