网络流之最大流
前言：网络流具有各种性质及应用，小艾在这个专题中将记录下最大流思想，并对其算法的正确性予以证明。
类型：最大流
题意：网络中的计算机s与计算机t通过其它若干计算机连接，两两计算机间有一条单向通信电缆并且有对应的1秒钟内所能传输的最大数据量。问当仅有计算机s向计算机t传输数据时，1秒内可传输的最大数据量。
分析：记每条通信电缆即边对应的最大数据传输量为c(e)，实际传输量为f(e)且f(e)满足条件0 <= f(e) <= c(e)。乍一看，该问题可以通过搜索解决：只要将s到t的所有可达路径找到，并选择一条最小边c(e)比其它路径的最小边都要大的路径进行本次数据传输f = c(e),然后修改该路径的相关数据即c(e')-f。重复上述操作直至不再有s到t的可达路径，那么便得到s到t的最大传输量。但是，分析可知，该算法效率低并且实现起来复杂，所以不建议采用。让我们再试试贪心算法：寻找任意一条满足f(e) < c(e)的可达路径,如果不存在满足条件的路径则算法结束，否则沿着该路径尽可能的增加c(e)直至算法结束。但这种贪心得到的答案是不正确的。我们可以对这样的贪心算法加以改进，即允许流回退。改进后的贪心算法如下：只利用满足f(e)
最大流算法的相关证明即最小割定理：
（1）割的概念：图的割(S, V\S)指从点集S出发指向S外部的边的集合，割的容量即这些边的容量之和。如果有s属于S,t属于V\S,此时的割又称为s-t的割。性质：如果将网络中s-t割所包含的边都删除，也就不再有s-t的可达路径，特别地满足这样条件的割中容量最小的称之为最小割。
（2）割与最大流的联系：设任意s-t的流f和任意的s-t的割（S, V\S）。f的流量=s出边的总流量, 对任意v属于S且v!=s恒有v的出边总流量=v的入边总流量，则f=S的出边总流量-S的入边总流量=割的容量-S的入边总流量。则f<=割的容量恒成立等价于f<=网络中的最小割。
（3）让我们考虑通过最大流算法所求得的f'。记流f'对应的残余网络中从s可达的顶点v组成的集合为S，由于f'对应的残余网络中不存在s-t的可达路径，故（S, V\S）是一个s-t的割。则割（S, V\S）中的边e有f'(e)=c(e)，而从V\S到S的边e应该有f'(e)=0(因反向边容量为c(e))。由此可得f'=S出边的总流量=割（S, V\S）的容量并且该割为此网络的最小割。
代码实现：//Ford_Fulkerson算法
//Ford_Fulkerson算法，O(FE)
#include
#include
using namespace std;
#define MV 1000
#define INF 10000
struct edge
{
int t, cap, rev; //rev用于确定反向边：反向边为G[t][rev]
edge(int to = 0, int c = 0, int r = 0) {t = to, cap = c, rev = r;}
};
vector
bool used[MV];
void add_es(int s, int t, int cap)
{
G[s].push_back(edge(t, cap, G[t].size()));//G[t].size(): (s,t)的反向边位于 t行G[t].size()列
G[t].push_back(edge(s, 0, G[s].size() - 1)); //G[s].size()-1: (t,s)的反向边位于 s行G[s].size()-1列
}
int min(int v1, int v2)
{
return v1 <= v2? v1 : v2;
}
int dfs(int v, int t, int f)
{//只需搜索任意一条从s到t的可达路径
if(v == t)
return f;
used[v] = true;
int size = G[v].size();
for(int i = 0; i < size; ++i)
{
edge &es = G[v][i]; //es必须引用&es,因es.cap -= d;
if(!used[es.t] && es.cap > 0)
{
int d= dfs(es.t, t, min(f, es.cap));
if(d > 0)
{
es.cap -= d;
G[es.t][es.rev].cap += d; //实现逆流回退 //****** es == G[v][i] 与 G[es.t][es.rev]互为反边
return d;
}
}
}
return 0;
}
int max_flow(int v, int n, int s, int t)
{
int i, j;
int flow = 0;
while(1)
{
memset(used, 0, sizeof(used));
int f = dfs(s, t, INF);
if(f == 0)
return flow;
flow += f;
}
}
void solve(int v, int n, int s, int t)
{
int i, j;
for(i = 0; i < n; ++i)
{
int s1, t1, cap;
cin >> s1 >> t1 >> cap;
add_es(s1, t1, cap);
}
cout << "最大流是："<< max_flow(v, n, s, t) << endl;
}
int main()
{
int v, n, s, t; //v个顶点 n条边 输入端s和输出端t
cin >> v >> n >> s >> t;
solve(v, n, s, t);
return 0;
}
//Dinic算法，O(VE)
#include
#include
#include
using namespace std;
#define MV 1000
#define INF 10000
struct edge
{
int t, cap, rev;
edge(int to = 0, int c = 0, int r = 0): t(to), cap(c), rev(r) {};
};
vector
int level[MV];
int iter[MV]; //当前弧优化：避免对一条没有用的边进行多次检查
//iter[v]含义：以v为起点的所有边中,第0至iter[v]-1都是没有用的边,有用边是iter[v]至G[v].size()-1
void add_es(int s, int t, int cap)
{
G[s].push_back(edge(t, cap, G[t].size()));
G[t].push_back(edge(s, 0, G[s].size() - 1));
}
int min(int v1, int v2)
{
return v1 <= v2? v1 : v2;
}
void bfs(int n, int v, int s)
{//构造分层图O(E),最多进行V-1次
queue
que.push(s);
level[s] = 0;
while(!que.empty())
{
int tv = que.front();
que.pop();
int size = G[tv].size();
for(int i = 0; i < size; ++i)
{
edge es = G[tv][i];
if(es.cap > 0 && level[es.t] == -1)
{
level[es.t] = level[tv] + 1;
que.push(es.t);
}
}
}
int dfs(int v, int t, int f)
{//寻找最短增广路O(E)
if(v == t)
return f;
int size = G[v].size();
for(int &i = iter[v]; i < size; ++i) //&i = iter[v]: 引用,iter[v]的值改变以记录有效边的起始点
{
edge &es = G[v][i];
if(es.cap > 0 && level[v] < level[es.t])
{
int d = dfs(es.t, t, min(f, es.cap));
if(d > 0)
{
es.cap -= d;
G[es.t][es.rev] += d;//******
return d;
}
}
}
return 0;
}
int max_flow(int n, int v, int s, int t)
{//求最大流O(VE)
int flow = 0;
while(1)
{
memset(level, -1, sizeof(level));
bfs(n, v, s);
if(level[t] == -1) //已经没有s-t的可达路径
return flow;
memset(iter, 0, sizeof(iter));
int f;
while((f = dfs(s, t, INF)) > 0)
flow += f;//******跳出循环时：最短增广路长度已经变长(继续寻找增广路)或不存在增广路(bfs后level[t] == -1)
}
void solve(int n, int v, int s, int t)
{
int i;
for(i = 0; i < n; ++i)
{
int s1, t1, cap;
cin >> s1 >> t1 >> cap;
add_es(s1, t1, cap);
}
cout << max_flow(n, v, s, t) << endl;
}
int main()
{
int n, v, s, t;
cin >> n >> v >> s >> t;
solve(n, v, s, t);
return 0;
}