下面是由一道题引发的一系列故事。。。
题目链接 http://poj.org/problem?id=1273
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 68920 | Accepted: 26683 |
Description
Input
Output
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
Sample Output
50
直接看输入输出。输入:n和m,分别代表边的数量和节点数。之后的n行,输入三个数,代表(u,v)边的最大水容量。要求输出,从起点1开始到终点m的最大水流量。那么,与实际相联系,很容易知道,对于每一条路径,都最大只能运输该路径上的最小容量的那条边所能承受的水量。所以,这个问题就是传说中的网络流之最大流问题。
经过查阅资料,先理清一下基本的概念:
容量网络:设G(V,E),是一个有向网络,在V中指定了一个顶点,称为源点(记为Vs),以及另一个顶点,称为汇点(记为Vt);对于每一条弧<u,v>属于E,对应有一个权值c(u,v)>0,称为弧的容量.通常吧这样的有向网络G称为容量网络.
弧的流量:通过容量网络G中每条弧<u,v>,上的实际流量(简称流量),记为f(u,v);
网络流:所有弧上流量的集合f={f(u,v)},称为该容量网络的一个网络流.
可行流:在容量网络G中满足以下条件的网络流f,称为可行流.
a.弧流量限制条件: 0<=f(u,v)<=c(u,v);
b:平衡条件:即流入一个点的流量要等于流出这个点的流量,(源点和汇点除外).
若网络流上每条弧上的流量都为0,则该网络流称为零流.
伪流:如果一个网络流只满足弧流量限制条件,不满足平衡条件,则这种网络流为伪流,或称为容量可行流.(预流推进算法有用)
最大流:在容量网络中,满足弧流量限制条件,且满足平衡条件并且具有最大流量的可行流,称为网络最大流,简称最大流.
弧的类型:
a.饱和弧:即f(u,v)=c(u,v);
b.非饱和弧:即f(u,v)<c(u,v);
c.零流弧:即f(u,v)=0;
d.非零流弧:即f(u,v)>0.
链:在容量网络中,称顶点序列(u1,u2,u3,u4,..,un,v)为一条链要求相邻的两个顶点之间有一条弧.
设P是G中一条从Vs到Vt的链,约定从Vs指向Vt的方向为正方向.在链中并不要求所有的弧的方向都与链的方向相同.
a.前向弧:(方向与链的正方向一致的弧),其集合记为P+,
b.后向弧:(方向与链的正方向相反的弧),其集合记为P-.
增广路:
设f是一个容量网络G中的一个可行流,P是从Vs到Vt 的一条链,若P满足以下条件:
a.P中所有前向弧都是非饱和弧,
b.P中所有后向弧都是非零弧.
则称P为关于可行流f 的一条增广路.
沿这增广路改进可行流的操作称为增广.
残留容量:给定容量网络G(V,E),及可行流f,弧<u,v>上的残留容量记为cl(u,v)=c(u,v)-f(u,v).每条弧上的残留容量表示这条弧上可以增加的流量.因为从顶点u到顶点v的流量减少,等效与从顶点v到顶点u的流量增加,所以每条弧<u,v>上还有一个反方向的残留容量cl(v,u)=-f(u,v).
残留网络:设有容量网络G(V,E)及其上的网络流f,G关于f的残留网络记为G(V',E').其中G'的顶点集V'和G中顶点集G相同,V'=V.对于G中任何一条弧<u,v>,如果f(u,v)<c(u,v),那么在G'中有一条弧<u,v>属于E',其容量为c'(u,v)=c(u,v)-f(u,v),如果f(u,v)>0,则在G'中有一条弧<v,u>属于E',其容量为c'(v,u)=f(u,v).残留网络也称为剩余网络.
为什么要有反向边呢?
我们第一次找到了1-2-3-4这条增广路,这条路上的delta值显然是1。于是我们修改后得到了下面这个流。(图中的数字是容量)
这时候(1,2)和(3,4)边上的流量都等于容量了,我们再也找不到其他的增广路了,当前的流量是1。
但这个答案明显不是最大流,因为我们可以同时走1-2-4和1-3-4,这样可以得到流量为2的流。
那么我们刚刚的算法问题在哪里呢?问题就在于我们没有给程序一个”后悔”的机会,应该有一个不走(2-3-4)而改走(2-4)的机制。那么如何解决这个问题呢?回溯搜索吗?那么我们的效率就上升到指数级了。
而这个算法神奇的利用了一个叫做反向边的概念来解决这个问题。即每条边(I,j)都有一条反向边(j,i),反向边也同样有它的容量。
我们直接来看它是如何解决的:
在第一次找到增广路之后,在把路上每一段的容量减少delta的同时,也把每一段上的反方向的容量增加delta。即在Dec(c[x,y],delta)的同时,inc(c[y,x],delta)
我们来看刚才的例子,在找到1-2-3-4这条增广路之后,把容量修改成如下
这时再找增广路的时候,就会找到1-3-2-4这条可增广量,即delta值为1的可增广路。将这条路增广之后,得到了最大流2。
那么,这么做为什么会是对的呢?我来通俗的解释一下吧。
事实上,当我们第二次的增广路走3-2这条反向边的时候,就相当于把2-3这条正向边已经是用了的流量给”退”了回去,不走2-3这条路,而改走从2点出发的其他的路也就是2-4。(有人问如果这里没有2-4怎么办,这时假如没有2-4这条路的话,最终这条增广路也不会存在,因为他根本不能走到汇点)同时本来在3-4上的流量由1-3-4这条路来”接管”。而最终2-3这条路正向流量1,反向流量1,等于没有流量。
这就是这个算法的精华部分,利用反向边,使程序有了一个后悔和改正的机会
第一个隆重登场的算法是 EK(Edmond—Karp)算法
感谢http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html 的博文,里面有很详细的我要给出的第一个代码的模板和对于该算法的深刻理解
先给出模板(也是为了方便以后自己查阅)
<strong><span style="font-size:12px;">#include <iostream>
#include <queue>
#include<string.h>
using namespace std;
#define arraysize 201
int maxData = 0x7fffffff;
int capacity[arraysize][arraysize]; //记录残留网络的容量
int flow[arraysize]; //标记从源点到当前节点实际还剩多少流量可用
int pre[arraysize]; //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中
int n,m;
queue<int> myqueue;
int BFS(int src,int des)
{
int i,j;
while(!myqueue.empty()) //队列清空
myqueue.pop();
for(i=1;i<m+1;++i)
{
pre[i]=-1;
}
pre[src]=0;
flow[src]= maxData;
myqueue.push(src);
while(!myqueue.empty())
{
int index = myqueue.front();
myqueue.pop();
if(index == des) //找到了增广路径
break;
for(i=1;i<m+1;++i)
{
if(i!=src && capacity[index][i]>0 && pre[i]==-1)
{
pre[i] = index; //记录前驱
flow[i] = min(capacity[index][i],flow[index]); //关键:迭代的找到增量
myqueue.push(i);
}
}
}
if(pre[des]==-1) //残留图中不再存在增广路径
return -1;
else
return flow[des];
}
int maxFlow(int src,int des)
{
int increasement= 0;
int sumflow = 0;
while((increasement=BFS(src,des))!=-1)
{
int k = des; //利用前驱寻找路径
while(k!=src)
{
int last = pre[k];
capacity[last][k] -= increasement; //改变正向边的容量
capacity[k][last] += increasement; //改变反向边的容量
k = last;
}
sumflow += increasement;
}
return sumflow;
}
int main()
{
int i,j;
int start,end,ci;
while(cin>>n>>m)
{
memset(capacity,0,sizeof(capacity));
memset(flow,0,sizeof(flow));
for(i=0;i<n;++i)
{
cin>>start>>end>>ci;
if(start == end) //考虑起点终点相同的情况
continue;
capacity[start][end] +=ci; //此处注意可能出现多条同一起点终点的情况
}
cout<<maxFlow(1,m)<<endl;
}
return 0;
}</span></strong>
对于BFS找增广路:
1. flow[1]=INF,pre[1]=0;
源点1进队列,开始找增广路,capacity[1][2]=40>0,则flow[2]=min(flow[1],40)=40;
capacity[1][4]=20>0,则flow[4]=min(flow[1],20)=20;
capacity[2][3]=30>0,则flow[3]=min(folw[2]=40,30)=30;
capacity[2][4]=30,但是pre[4]=1(已经在capacity[1][4]这遍历过4号点了)
capacity[3][4].....
当index=4(汇点),结束增广路的寻找
传递回increasement(该路径的流),利用前驱pre寻找路径
路径也自然变成了这样:
2.flow[1]=INF,pre[1]=0;
源点1进队列,开始找增广路,capacity[1][2]=40>0,则flow[2]=min(flow[1],40)=40;
capacity[1][4]=0!>0,跳过
capacity[2][3]=30>0,则flow[3]=min(folw[2]=40,30)=30;
capacity[2][4]=30,pre[4]=2,则flow[2][4]=min(flow[2]=40,20)=20;
capacity[3][4].....
当index=4(汇点),结束增广路的寻找
传递回increasement(该路径的流),利用前驱pre寻找路径
图也被改成
接下来同理
这就是最终完成的图,最终sumflow=20+20+10=50(这个就是最大流的值)
下面是我用这个方法写的本题的代码
<strong><span style="font-size:12px;">#include <cstdio>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
int const MAX = 1005;
int const inf = 0x3f3f3f3f;
int c[MAX][MAX];//c[u][v]保存容量
int f[MAX][MAX];//f[u][v]保存当前流量
int a[MAX];// a数组在每趟bfs中找到最小路径中最小残余流量的,a数组使个递推数组,a[v]的意思是从源点s到点v的最小残余流量
int p[MAX];//保存前一个点
int n, m;
int bfs(int s, int t)
{
queue<int> q;
int flow = 0;
while(!q.empty()) q.pop();
memset(f, 0, sizeof(f));
while(1){
memset(a, 0, sizeof(a));
a[s] = inf;//将起始点的最小残余量设为最大
q.push(s);
while(!q.empty()){//bfs找到一条最短路,这里的边不代表距离,可以看作每两个点都是单位距离的
int u;
u = q.front();
q.pop();
for(int v = 1; v <= m; v++){//枚举所有点v <u,v>
if(!a[v] && c[u][v] > f[u][v]){//a[]可以代替vis[],来判断这个点是否已经遍历过,后面那个条件更是起了关键作用,很巧妙
p[v] = u;
q.push(v);
a[v] = min(a[u], c[u][v] - f[u][v]);//递推
}
}
}
if(!a[t]) break;//直到最小残余流量为0时,退出
for(int u = t; u != s; u = p[u]){
f[p[u]][u] += a[t];
f[u][p[u]] -= a[t];
}
flow += a[t];
}
return flow;
}
int main()
{
while(~scanf("%d %d", &n, &m)){
memset(c, 0, sizeof(c));
memset(p, 0, sizeof(p));
for(int i = 1; i <= n; i++){
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
c[u][v] += w;
}
printf("%d\n", bfs(1, m));
}
return 0;
}</span></strong>
基于邻接矩阵的一个模板
<strong><span style="font-size:12px;">#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int map[300][300];
int used[300];
int n,m;
const int INF = 1000000000;
int dfs(int s,int t,int f)
{
if(s == t) return f;
for(int i = 1 ; i <= n ; i ++) {
if(map[s][i] > 0 && !used[i]) {
used[i] = true;
int d = dfs(i,t,min(f,map[s][i]));
if(d > 0) {
map[s][i] -= d;
map[i][s] += d;
return d;
}
}
}
}
int maxflow(int s,int t)
{
int flow = 0;
while(true) {
memset(used,0,sizeof(used));
int f = dfs(s,t,INF);//不断找从s到t的增广路
if(f == 0) return flow;//找不到了就回去
flow += f;//找到一个流量f的路
}
}
int main()
{
while(scanf("%d%d",&m,&n) != EOF) {
memset(map,0,sizeof(map));
for(int i = 0 ; i < m ; i ++) {
int from,to,cap;
scanf("%d%d%d",&from,&to,&cap);
map[from][to] += cap;
}
cout << maxflow(1,n) << endl;
}
return 0;</span>
}</strong>
<span style="font-size:12px;"><strong>#include <cstdio>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int const inf = 0x3f3f3f3f;
int const MAX = 300;
struct Node
{
int to; //与这个点相连的点
int cap; //以这个射出的边的容量
int rev; //这个点的反向边
};
vector<Node> v[MAX];
bool used[MAX];
void add_node(int from, int to, int cap)//重边情况不影响
{
v[from].push_back((Node){to, cap, v[to].size()});
v[to].push_back((Node){from, 0, v[from].size() - 1});
}
int dfs(int s, int t, int f)
{
if(s == t)
return f;
used[s] = true;
for(int i = 0; i < v[s].size(); i++){
Node &tmp = v[s][i];
if(used[tmp.to] == false && tmp.cap > 0){
int d = dfs(tmp.to, t, min(f, tmp.cap));
if(d > 0){
tmp.cap -= d;
v[tmp.to][tmp.rev].cap += d;
return d;
}
}
}
return 0;
}
int max_flow(int s, int t)
{
int flow = 0;
while(1){
memset(used, false, sizeof(used));
int f = dfs(s, t, inf);
if(f == 0)
return flow;
flow += f;
}
return flow;
}
int main()
{
int n, m;
while(scanf("%d %d", &n, &m) != EOF){
for(int i = 0; i <= m; i++)
v[i].clear();
int u1, v1, w;
for(int i = 1; i <= n; i++){
scanf("%d %d %d", &u1, &v1, &w);
add_node(u1, v1, w);
}
printf("%d\n", max_flow(1, m));
}
return 0;
}</strong></span>
第三种方法:Dinic算法,可以看作是两种方法的结合体,它进行了一定的优化,对于某些横边多的图,运行速度方面得到了大幅提升
在层次图中使用DFS进行增广直到不存在增广路
重复以上步骤直到无法增广
<span style="font-size:12px;"><strong>#include <cstdio>
#include <string.h>
#include <queue>
using namespace std;
int const inf = 0x3f3f3f3f;
int const MAX = 205;
int n, m;
int c[MAX][MAX], dep[MAX];//dep[MAX]代表当前层数
int bfs(int s, int t)//重新建图,按层次建图
{
queue<int> q;
while(!q.empty())
q.pop();
memset(dep, -1, sizeof(dep));
dep[s] = 0;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
for(int v = 1; v <= m; v++){
if(c[u][v] > 0 && dep[v] == -1){//如果可以到达且还没有访问,可以到达的条件是剩余容量大于0,没有访问的条件是当前层数还未知
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[t] != -1;
}
int dfs(int u, int mi, int t)//查找路径上的最小流量
{
if(u == t)
return mi;
int tmp;
for(int v = 1; v <= m; v++){
if(c[u][v] > 0 && dep[v] == dep[u] + 1 && (tmp = dfs(v, min(mi, c[u][v]), t))){
c[u][v] -= tmp;
c[v][u] += tmp;
return tmp;
}
}
return 0;
}
int dinic()
{
int ans = 0, tmp;
while(bfs(1, m)){
while(1){
tmp = dfs(1, inf, m);
if(tmp == 0)
break;
ans += tmp;
}
}
return ans;
}
int main()
{
while(~scanf("%d %d", &n, &m)){
memset(c, 0, sizeof(c));
int u, v, w;
while(n--){
scanf("%d %d %d", &u, &v, &w);
c[u][v] += w;
}
printf("%d\n", dinic());
}
return 0;
}</strong></span>
文章浏览阅读1.4w次,点赞2次,收藏15次。NoVncNoVnc Web 端的Vnc软件、可以直接通过网页访问远程主机,采用 HTML5、WebSockets、Canvas和 JavaScript 实现,被普遍用在各大云平台中。 访问 Vnc 服务、需要做 tcp 到websockts的转化 才能在Html中看出来。网页就是一个客户端、类似 Windows 下的 vncviewer , 只是此时填的不是裸露的 VNC 服务的..._novnc网页版
文章浏览阅读2k次。爱心代码_hbuilder爱心代码
文章浏览阅读8.4k次。自己一直从事页游开发看到一篇做游戏服务端的开发文章自然要收录下.(本文算是记录的蛮详细的,不过具体的性能优化,缓存,消息的处理等都不在其中,整体宏观列出了.)本文来源于网络,好久之前看的,被收藏后一直没有看,今天看了后收藏到网站,原文地址:http://kakaluyi.iteye.com/blog/1489592.一、网络 网络游戏,首先面临的问题当然是如何进行网络通信。首先考虑_java游戏同时在线
文章浏览阅读2.7k次。VMware里默认是640×480的分辨率。复制文件过程大概持续了三分多钟。然后就是重新启动。_windowsme还有人用吗
文章浏览阅读3k次。软件架构师,2022版新教材部分知识点_系统架构师
文章浏览阅读1w次,点赞5次,收藏24次。1、示例POJO类用户类User,其中包含一个狗的引用package org.springframework.cn.shu.edu.pojo;public class User { String username; String password; Dog dog; public String getUsername() { retu..._defaultlistablebeanfactory beanfactory = new defaultlistablebeanfactory();
文章浏览阅读7.6k次,点赞7次,收藏15次。大家好!我最近在使用Windows系统时遇到了一个常见的问题,就是执行exe文件时窗口一闪而过,无法正确运行程序。经过一番搜索和尝试,我找到了解决这个问题的方法,现在与大家分享一下。首先,这个问题通常是由于某些错误配置或冲突引起的。_exe文件打开一闪就没了
文章浏览阅读1.2k次。闪屏的作用闪屏产生之初,是因为当用户点击一个应用后,应用打开会有一个加载过程,而这个过程中程序一直处于“加载中”状态,这个默认的界面当然对用户是不友好的,为了让用户明白自己已经打开了应用, 并且“舒适的等待”,应用会使用一张默认图代替加载过程,而有些应用为了让自己看起来加载的更快些,会机智采用一张首页框架图~由于闪屏的大量使用,针对闪屏的设计也应运而生,从体验角度讲,尽快打开APP才是正确的处理方法_android splashscree闪屏页
文章浏览阅读5.3k次,点赞64次,收藏99次。【代码】MATLAB 之 二维图形绘制的基本函数和辅助操作。_matlab绘制二维曲线
文章浏览阅读525次。万字谈监控:解答Zabbix与Prometheus选型疑难原创 deeplus DBAplus社群读完本文,你将收获两者适用于多大规模的监控场景?超过5000以上监控节点时怎么办?高可用怎么解决?两者怎么解决存储问题?对于监控信息是否有历史存储和分析,能从历史信息中挖掘到哪些有价值的信息?两者怎么应对告警风暴和误报?在智能监控和自动治愈方面是否有可借鉴的实践?基于什么算法或策略?怎么进行故障预判和预处理?监控大屏是怎么设计的?自动化运维管理是两者同时使用还是二选一更合适?两者在配合使用时_zabbix 告警风暴抑制
文章浏览阅读1.5k次。全文共4912字,预计学习时长15分钟图源:Unsplash新年到,又到了给自己定制新年目标的时候了。今年,你打算给自己树什么样的flag,不,是目标呢?多读书多看报,少吃零食多睡觉?要么读书,要么旅行,身体和灵魂总有一个在路上?对于每个人来说,书都是必不可少的精神食粮。读书=充电。今天,小芯就为大家整理了25本数据科学领域最..._数据和歌利亚:一场争夺数据和控制世界的无烟之战 pdf
文章浏览阅读5.1k次,点赞6次,收藏3次。Non-XML response from server. Response code: 502, Content-Type: null, body: <Error> <Code>AccessDenied</Code> <Message>S3 API Request made to Console port. S3 Requests should be sent to API port.</Message> <Request_non-xml response from server. response code: 400, content-type: text/xml; ch