网络流 最大流问题 最短路径最大流问题 最小费用最大流问题 专项总结
一道水题的题目链接：http://poj.org/problem?id=1273 就先拿这个入手吧。
可知我们是要求从1号点到n号点最大的水流量。
那么我们怎么去找这个最大流量呢？
基本的思路就是在路的最大流量允许的情况下一直不断的添加流量，直达我们无法添加为止。
但是有的时候我们会发现找到的一条从起点到终点的流截断了其他可能的流，比如下图：
这下我们就无法继续扩容了，原因就是因为我们错误的选择了一条路径。 那么我们怎么才能消除这种错误的选择呢？ 于是有神犇提出了反向加边，构造残余网络的 Ford-Fulkerson 算法。
残余网络 (Residual Network) 在一个网络流图上，找到一条源到汇的路径 （即找到了一个流量）后，对路径上所有的 边，其容量都减去此次找到的流量，对路径上所有的边，都添加一条反向边，其容量也 等于此次找到的流量，这样得到的新图，就称为原图的“残余网络”
Ford-Fulkerson算法 求最大流的过程，就是不断找到一条源到汇 的路径，然后构建残余网络，再在残余网络上寻找新的路径，使总流量增加，然后形成新的残余网络，再寻找新路径。直到某个残余网络上找不到从源到汇的路径为止，最大流就算出来了。
每次寻找新流量并构造新残余网络的过程， 就叫做寻找流量的“增广路径”，也叫“增广”
反向加边后的残余网络为：
至此最大流的基本做法就叙述完了，先敲个基本代码过一下那个水题。
首先使用dfs来试一下，然后你会见到万恶的 ：Time Limit Exceeded
超时代码：
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=201;
int n,m;
int s,e,c;
int map1[maxn][maxn];
int maxflow=0;
bool vis[maxn];
int pre[maxn];
bool dfs(int ss)
{
if(ss==m)return 1;
for(int i=1;i<=m;i++)
{
if(!vis[i]&&map1[ss][i]>0)
{
pre[i]=ss;
vis[i]=1;
if(dfs(i))return 1;
vis[i]=0;
}
}
return 0;
}
int Augment()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
{
pre[i]=i;
}
vis[1]=1;
bool flag=dfs(1);
//如果存在增广路径的话
if(flag)
{
//找到最小流量
int minflow=inf;
int t=m;
while(pre[t]!=t)
{
minflow=min(map1[pre[t]][t],minflow);
t=pre[t];
}
//正向减边，反向加边，构建残余网络
t=m;
while(pre[t]!=t)
{
map1[pre[t]][t]-=minflow;
map1[t][pre[t]]+=minflow;
t=pre[t];
}
return minflow;
}
else
return 0;
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d %d",&n,&m))
{
maxflow=0;
memset(map1,0,sizeof(map1));
for(int i=0;i!=n;i++)
{
scanf("%d %d %d",&s,&e,&c);
map1[s][e]+=c;
}
int t=Augment();
while(t)
{
maxflow+=t;
t=Augment();
}
cout<<maxflow<<endl;
}
return 0;
}
原因在于我们的dfs搜素次数很多，有的时候反复取消添加同一条边，导致我们的效率大大降低。
如下图的情况：
其中B->C这个边在最坏情况下就一直在添加取消，添加取消。。。
所以我们又有Edmonds-Karp 最短增广路算法 在每次增广的时候，选择从源到汇的具有最少边数的增广路径,即不是通过dfs寻找增广路径，而是通过bfs寻找增广路径
代码：
#include
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=201;
int n,m;
int s,e,c;
int map1[maxn][maxn];
int maxflow=0;
bool vis[maxn];
int pre[maxn];
bool bfs()
{
queue q;
q.push(1);
vis[1]=1;
while(q.size())
{
int p = q.front();
q.pop();
if(p==m)return 1;
for(int i=1;i<=m;i++)
{
if(!vis[i]&&map1[p][i]>0)
{
pre[i]=p;
vis[i]=1;
q.push(i);
}
}
}
return 0;
}
int Augment()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
{
pre[i]=i;
}
vis[1]=1;
bool flag=bfs();
//如果存在增广路径的话
if(flag)
{
//找到最小流量
int minflow=inf;
int t=m;
while(pre[t]!=t)
{
minflow=min(map1[pre[t]][t],minflow);
t=pre[t];
}
//正向减边，反向加边，构建残余网络
t=m;
while(pre[t]!=t)
{
map1[pre[t]][t]-=minflow;
map1[t][pre[t]]+=minflow;
t=pre[t];
}
return minflow;
}
else
return 0;
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d %d",&n,&m))
{
maxflow=0;
memset(map1,0,sizeof(map1));
for(int i=0;i!=n;i++)
{
scanf("%d %d %d",&s,&e,&c);
map1[s][e]+=c;//注意这里改成了加等才能过，可能有重边，你敢信！？
}
int t=Augment();
while(t)
{
maxflow+=t;
t=Augment();
}
cout<<maxflow<<endl;
}
return 0;
}
你以为这就已经最快了吗？ 不不不，我们在每一次的bfs难道不是可以用好多次的吗？ 不需要bfs一次增广一次。 这就是Dinic 算法 ： 利用 BFS对残余网络分层，分完层后，利用DFS从前 一层向后一层反复寻找增广路。
其实更贪心一些还能优化，但是已经没什么必要了
#include
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=201;
int n,m;
int s,e,c;
int map1[maxn][maxn];
int maxflow=0;
bool vis[maxn];
int pre[maxn];
int layer[maxn];
bool bfs()
{
memset(layer,0,sizeof(layer));
queue q;
q.push(1);
vis[1]=1;
int maxlayer=inf;
while(q.size())
{
int p = q.front();
q.pop();
if(p==m)maxlayer=layer[p];
if(layer[p]>maxlayer)continue;
for(int i=1;i<=m;i++)
{
if(!vis[i]&&map1[p][i]>0)
{
vis[i]=1;
layer[i]=layer[p]+1;
q.push(i);
}
}
}
return layer[m];
}
int dfs(int ss,int minf)
{
vis[ss]=1;
if(ss==m)return minf;
for(int i=1;i<=m;i++)
{
if(!vis[i]&&map1[ss][i]>0&&layer[i]>layer[ss]&&layer[i])
{
pre[i]=ss;
int t = dfs(i,min(map1[ss][i],minf));
if(t)return t;
}
}
return 0;
}
void fresh()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
{
pre[i]=i;
}
}
void Dinic()
{
fresh();
maxflow=0;
//如果可以继续分层的话
while(bfs())
{
//dfs增广并 找到最小流量
fresh();
int minflow=dfs(1,inf);
while(minflow)
{
//正向减边，反向加边，狗杂残余网络
int t=m;
while(pre[t]!=t)
{
map1[pre[t]][t]-=minflow;
map1[t][pre[t]]+=minflow;
t=pre[t];
}
maxflow+=minflow;
fresh();
minflow=dfs(1,inf);
}
fresh();
}
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d %d",&n,&m))
{
maxflow=0;
memset(map1,0,sizeof(map1));
for(int i=0;i!=n;i++)
{
scanf("%d %d %d",&s,&e,&c);
map1[s][e]+=c;
}
Dinic();
cout<<maxflow<<endl;
}
return 0;
}
要求出最大流中每条边的流量，怎么办？ 好好利用最后的残余网络。 将原图备份，原图上的边的容量减去做完最大流的残余网络上的边的剩余容量，就是边的流量。
上面就是最最基本的最大流问题。
对于多源点，多汇点的问题可以添加超级源点和超级汇点，来总和流的计算。
再来一道水题：http://poj.org/problem?id=2112
题目告诉我们这里有K个milking machine，有C头牛，每台miking machine最多一天可以处理K头牛。 k个milking machine用1-k来编号， c头牛用k+1-k+c 来编号 下面K+C行分别是，第 i 个实体到第 j 个实体的距离 让后让你求一下所有牛到milking machine的最大距离的最小值。
就是让跑的最远才到miking machine的那头牛尽量少跑一点路。
可知我们至少得为每头牛分一个milking machine，总的流得能达到c。 并且我们所有流中过的路径长度越短越好。 那么我们需要二分枚举最长的长度，求出这个最长长度最短。
其实，这道题就是加一个超级源点，源点到每头牛的流是1， 加一个超级汇点，每个milking machine到超级汇点的流为m
你看就又成最大流问题了。不过我们要求路径长度最短。
那么我们需要： 先假定一个最大距离的的最小值 maxdist, 如果奶牛节点i和挤奶器节点j之间的距离<= maxdist,则从i节点连一条边到j节点，表示奶牛i可以 到挤奶器j去挤奶。该边容量为1。该图上的最大流如 果是C(奶牛数），那么就说明假设的 maxdist成立， 则减小 maxdist再试
总之，要二分 maxdist, 对每个maxdist值，都重新构 图，看其最大流是否是C，然后再决定减少或增加 maxdist 。
先来一份大佬的代码： 我打了详细注释了。略有改动，是为了可读性。
感谢：呆呆的人v http://blog.sina.com.cn/s/blog_691ce2b701018kqp.html
跑下来的成绩： 740K 1485MS
一会儿再自己写一份。
#include
#include
#define Max 300
#define inf 0x3f3f3f3f;
int dist[Max][Max],mat[Max][Max],pre[Max];
int K,C,M,src,des;
void Build (int num) //建图
{
//mat指的是流量
memset (mat,0,sizeof(mat));
//在当前路径下能走一路线
//遍历所有牛
for (int i = 1+K; i <= des-1; i ++)
{
//遍历所有机器
for (int j = 1; j <= K; j ++)
{
//如果牛到机器的距离小于我们的midlen，那么我们就把这个流设置为1
if (dist[i][j] <= num)
mat[i][j] = 1;
}
}
//与汇点相边,设置机器到超级汇点的流量为m
for (int i = 1; i <= K; i ++)
{
mat[i][des] = M;
}
//设置查集源点到所有牛的流量为1
for (int i = 1+K; i <= des-1; i ++) //与源点相连
{
mat[src][i] = 1;
}
}
bool BFS ()
{
//广搜找到增广路径
//设置父亲节点为-1
//memset(pre,-1,sizeof(pre))
memset (pre,0xff,sizeof(pre));
int que[Max];
//使用数组形式的循环队列
int front = 0,rear = 0;
//把起点的pre设置为自己
pre[src] = 0;
//把起点加入到队列
que[rear++] = src;
//当队列中还有元素的时候就不断搜索
while (front != rear)
{
int u = que[front++];
front = front % Max;
for (int v = 1; v <= des; v ++)
{
if (pre[v] != -1||mat[u][v] == 0)
continue;
pre[v] = u;
if (v == des)
return true;
que[rear++] = v;
rear = rear % Max;
}
}
return false;
}
int EK () //EK算法 每回增广的容量只能1
{
int ans = 0,i;
//使用广搜不断增广
while (BFS())
{
ans += 1;
for (i = des; i != src; i = pre[i])
{
mat[pre[i]][i] -= 1;
mat[i][pre[i]] += 1;
}
}
return ans;
}
void floyd()
{
int i,j,k;
for (k = 1; k <= des-1; k ++) //floyd
{
for (i = 1; i <= des-1; i ++)
{
for (j = 1; j <= des-1; j ++)
{
if (dist[i][j] > dist[i][k]+dist[k][j])
dist[i][j] = dist[i][k]+dist[k][j];
}
}
}
}
int main ()
{
int i,j,k;
while (~scanf ("%d%d%d",&K,&C,&M))
{
src = 0,des = K + C + 1;
for (i = 1; i <= K+C; i ++)
{
for (j = 1; j <= K+C; j ++)
{
scanf ("%d",&dist[i][j]);
//如果距离为0，就设置距离为inf
if (dist[i][j] == 0)
dist[i][j] = inf;
}
}
floyd();
int l = 0,r = 10000;
int ans = 0;
int count = 0;
while (l <= r) //二分
{
int mid = (l + r)>>1;
//根据我们允许的最远距离建流量图
Build (mid);
//求出最大流
int sum = EK(); //sum 表示有多少牛能走到挤奶机
if (sum == C) //表示 全部的牛都能走到
{
ans = mid; //当前的距离符合
r = mid - 1;
}
else
l = mid + 1;
}
printf ("%d
",ans);
}
return 0;
}
自己找到自己的错误所在之后又用Dinic敲了一遍，优化比那位大佬的性能要好一点： 成绩：648K 157MS
代码：
#include
#include
#include
#include
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn=250;
int n,k,c,m;
int map1[maxn][maxn];
int flowmap[maxn][maxn];
int pre[maxn];
int maxflow;
int minlen,midlen,maxlen;
int layer[maxn];
void build()
{
memset(flowmap,0,sizeof(flowmap));
for(int i=k+1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
if(map1[i][j]<=midlen)
flowmap[i][j]=1;
}
}
for(int i=1;i<=k;i++)
{
flowmap[i][n+1]=m;
}
for(int i=k+1;i<=n;i++)
{
flowmap[0][i]=1;
}
}
bool bfs()
{
memset(layer,0,sizeof(layer));
queue q;
int maxlayer=inf;
layer[0]=1;
q.push(0);
while(q.size())
{
int p=q.front();
q.pop();
if(layer[p]>maxlayer)continue;
if(p==n+1)
{
maxlayer=layer[p];
}
for(int i=0;i<=n+1;i++)
{
if(!layer[i]&&flowmap[p][i]>0)
{
layer[i]=layer[p]+1;
q.push(i);
}
}
}
return layer[n+1];
}
void dfsinit()
{
memset(pre,-1,sizeof(pre));
}
bool dfs(int ss)
{
if(ss==n+1)return 1;
for(int i=0;i<=n+1;i++)
{
if(layer[i]>layer[ss]&&flowmap[ss][i]>0)
{
pre[i]=ss;
bool flag = dfs(i);
if(flag)return 1;
}
}
return 0;
}
void Dinic()
{
maxflow=0;
while(bfs())
{
dfsinit();
while(dfs(0))
{
int t=n+1;
while(pre[t]!=-1)
{
flowmap[pre[t]][t]--;
flowmap[t][pre[t]]++;
t=pre[t];
}
maxflow++;
dfsinit();
}
}
}
void bsearch()
{
minlen=0;maxlen=100000;
while(minlen!=maxlen)
{
midlen=(minlen+maxlen)/2;
build();
Dinic();
if(maxflow==c)
{
maxlen=midlen;
}
else
{
minlen=midlen+1;
}
}
}
void floyd()
{
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int td=map1[i][k]+map1[k][j];
if(td<map1[i][j])
{
map1[i][j]=td;
}
}
}
}
}
int main()
{
while(~scanf("%d %d %d",&k,&c,&m))
{
n=k+c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&map1[i][j]);
if(!map1[i][j])
{
map1[i][j]=inf;
}
}
}
floyd();
bsearch();
cout<<minlen<<endl;
}
return 0;
}
下面我们再来看看网络流到底一般考什么。
再来一道水题： http://acm.hi-54.com/contest_problem.php?cid=1457&pid=4 这个是河南省第十一届ACM省赛的题。
类型是最小费用最大流问题。
照惯例我还是来给一个大佬的神犇代码打打注释。
感谢：Tony5t4rk https://blog.csdn.net/tony5t4rk/article/details/82947395
#include
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
//设计了边的结构体，用来在Spfa时使用
//V表示下一个点，Cap表示总容量capacity，Cost用来表示这条路单位货物运输需要花费多少，
//Flow表示现在这条路加上了多少流量，Next表示我们大家都是以U点开始的集合的，上一个路
//这份代码的巧妙就是用next把本来分散的路径数据通过Next划分成了，以不同点开始的路的集合
//Next指的是上一条以U点开始的路径在edges数组的第几行。
//详细解释见Addedge（）
struct Link
{
long long V, Cap, Cost, Flow, Next;
};
//N指的是有几个仓库
int N;
//A用来记录有货物的地点，B记录哪里需要货物
int A[maxn], B[maxn];
//Head用来记录以U开始的边的最后一条在edges数组中的第几行
int Head[maxn];
//Path用来记录在增广时用Spfa搜出来的路径
int Path[maxn];
//Dis用来记录到超级源点的距离，就是dijkstra里边用的那个Dis
int Dis[maxn];
//Vis是在Spfa广搜时用来标记时用的
bool Vis[maxn];
//Tot用来记录总共我们存到edges中了几条边
int Tot;
//用来存边
Link edges[maxn << 3];
//初始化，把路径总数Tot初始话为0
//把Head全部初始化为-1，表示还没有从U点开始的路径
void Init()
{
Tot = 0;
memset(Head, -1, sizeof(Head));
}
//加边函数，精华
void AddEdge(int U, int V, long long Cap, long long Cost)
{
//Tot这一行存进去我们要加的这条边，并把以U开始的上一条边的行数存在了Next中，
//这样我们很容易遍历到所有以U开始的边，从而进行深搜。
//那么疑问来了我们为啥不直接开vector edges[maxn]这样储存呢，这样又清晰，又省内存，也快
//因为我们在网络流问题中很容易涉及到残余网络的反向边，如果我们采用vector存
//那么我们在找反向边时该怎么办呢?
//扫描一遍edges[v]？ 慢死了
//下面这份代码处理找反向边的神仙操作就来了
edges[Tot] = Link {V, Cap, Cost, 0, Head[U]};
Head[U] = Tot++;
//正向加了一条偶数行的正向边后，又加了一条行数为奇数的反向边
//花费为负值，用来在取消流时使用。但反向边一开始时是没有容量的，即不能直接在这条边上加流
//只能取消这上面由于反向加边产生的流
//由于我们这样的建边方式，那么edges[i]这条边的反向边就是edges[i^1]，不解释，可好玩
edges[Tot] = Link {U, 0, -Cost, 0, Head[V]};
Head[V] = Tot++;
}
//可知我们的图总共分四层
//超级源点一层，
//有货的一层
//缺货的一层
//超级汇点一层
//我们使用广搜，必定是严格按照一层一层的搜索的，不解释
//那么我们怎么才能正确的进行增广呢？
//我们的最终目的是要找到最小费用的最大流
//那么我们是不是可以在找增广路径的时候使用贪心的思想，
//假如找到的每一条增广路径都是当前能找到的花费最小的增广路，那么我们的最终花费不就一定是最小的了吗
//因为如果我们加了一条不是当前最小花费的流，那么他必定会反向加边，
//那么我们在下一轮的搜索中必定会找到，这个不太聪明的流而反向取消他
//所以贪心的去搜索当前花费最小的流就好
//那么我们怎么找当前花费最小的路径呀，我们用Path来标记到当前节点，运输单位物资花费最小的点
//用Dis来保存到当前节点，运输单位物资花费最小的值
//当前点的花费一定是 所有上一层节点中的（Dis+到当前节点花费）的最小值。
//然后我们就相当于构建了一个已经在最小花费的集合的点集，和不在最小花费点集的一个点集
//然后使用当前这个点来优化那些不在当前最小花费点集的那些点。
//思想就是dijkstra的最短路径思想
//最终我们就找到了一条从超级源点，到超级汇点的最小单位花费的一条路径。
//之后进行增广就好啦
bool Spfa(int Start, int End)
{
memset(Dis, INF, sizeof(Dis));
memset(Vis, false, sizeof(Vis));
memset(Path, -1, sizeof(Path));
Dis[Start] = 0;
Vis[Start] = true;
std::queue Que;
while (!Que.empty())
{
Que.pop();
}
Que.push(Start);
while (!Que.empty())
{
int U = Que.front();
Que.pop();
Vis[U] = false;
for (int i = Head[U]; i != -1; i = edges[i].Next)
{
int V = edges[i].V;
if (edges[i].Cap > edges[i].Flow && Dis[V] > Dis[U] + edges[i].Cost)
{
Dis[V] = Dis[U] + edges[i].Cost;
Path[V] = i;
if (!Vis[V])
{
Vis[V] = true;
Que.push(V);
}
}
}
}
return Path[End] != -1;
}
//这个没啥好解释的嘛
//就是使用Spfa找到花费最小的那个路，进行增广就好
//让后正向减边，反向加边就好
//至于找反向边按个骚操作也解释过了
int MinCostMaxFlow(int Start, int End, long long &MinCost)
{
int MaxFlow = 0;
MinCost = 0;
while (Spfa(Start, End))
{
int Min = INF;
for (int i = Path[End]; i != -1; i = Path[edges[i ^ 1].V])
{
if (edges[i].Cap - edges[i].Flow < Min) {
Min = edges[i].Cap - edges[i].Flow;
}
}
for (int i = Path[End]; i != -1; i = Path[edges[i ^ 1].V]) {
edges[i].Flow += Min;
edges[i ^ 1].Flow -= Min;
MinCost += edges[i].Cost * Min;
}
MaxFlow += Min;
}
return MaxFlow;
}
int main(int argc, char *argv[])
{
while (~scanf("%d", &N))
{
Init();//head=-1 Tot=0
for (int i = 1; i <= N; ++i)
{
scanf("%d", &A[i]);
AddEdge(0, i, A[i], 0);//初始化超级源点到a
}
for (int i = 1; i <= N; ++i)
{
scanf("%d", &B[i]);
AddEdge(i, N + 1, B[i], 0);//初始化b到超级汇点
}
//添加题目给的费用路径
for (int i = 1, U, V, C; i < N; ++i)
{
scanf("%d%d%d", &U, &V, &C);
AddEdge(U, V, INF, C);
AddEdge(V, U, INF, C);
}
long long MinCost;
//计算最小费用最大流
MinCostMaxFlow(0, N + 1, MinCost);
printf("%lld
", MinCost);
}
return 0;
}
其实我一开始在做这个题目的时候首先想到的是先处理一下输入数据。 0 1 2 2 0 0 0 0 1 1 1 1 第一行是当前货物的分配 第二行是目的达到的状态 可知有一些货物根本不需要动，不必考虑 那么数据就变成了： 0 1 1 1 0 0 0 0 0 0 1 1 这样就只是存粹的从有货的地方往没货的地方运就好了。 超级源点一层 有货的一层 缺货的一层 超级汇点一层。 十分清晰 上边大佬那份代码并没有处理，也就是说大佬的那个层次中，有的点既在第二次有货层，也在第三层缺货层。这样我们的Spfa从源点一次搜索就能搜到缺货层，两次搜索就能搜索到超级汇点。 不知道会不会产生，本来自己仓库需要的货物往别人那里送的情况。我猜是有可能的，此处不再论述。 反正我们都已经把数据都存在数组A，B中了为何不做一些优化呢？ 优化后网络层次更清晰，并且避免了有些仓库傻傻的把自己需要的货物送给别人的浪费错误。 加快了算法的速度。
经测试，这么简单的一个优化后，算法速度提高了一倍
#include
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
//设计了边的结构体，用来在Spfa时使用
//V表示下一个点，Cap表示总容量capacity，Cost用来表示这条路单位货物运输需要花费多少，
//Flow表示现在这条路加上了多少流量，Next表示我们大家都是以U点开始的集合的，上一个路
//这份代码的巧妙就是用next把本来分散的路径数据通过Next划分成了，以不同点开始的路的集合
//Next指的是上一条以U点开始的路径在edges数组的第几行。
//详细解释见Addedge（）
struct Link
{
long long V, Cap, Cost, Flow, Next;
};
//N指的是有几个仓库
int N;
//A用来记录有货物的地点，B记录哪里需要货物
int A[maxn], B[maxn];
//Head用来记录以U开始的边的最后一条在edges数组中的第几行
int Head[maxn];
//Path用来记录在增广时用Spfa搜出来的路径
int Path[maxn];
//Dis用来记录到超级源点的距离，就是dijkstra里边用的那个Dis
int Dis[maxn];
//Vis是在Spfa广搜时用来标记时用的
bool Vis[maxn];
//Tot用来记录总共我们存到edges中了几条边
int Tot;
//用来存边
Link edges[maxn << 3];
//初始化，把路径总数Tot初始话为0
//把Head全部初始化为-1，表示还没有从U点开始的路径
void Init()
{
Tot = 0;
memset(Head, -1, sizeof(Head));
}
//加边函数，精华
void AddEdge(int U, int V, long long Cap, long long Cost)
{
//Tot这一行存进去我们要加的这条边，并把以U开始的上一条边的行数存在了Next中，
//这样我们很容易遍历到所有以U开始的边，从而进行深搜。
//那么疑问来了我们为啥不直接开vector edges[maxn]这样储存呢，这样又清晰，又省内存，也快
//因为我们在网络流问题中很容易涉及到残余网络的反向边，如果我们采用vector存
//那么我们在找反向边时该怎么办呢?
//扫描一遍edges[v]？ 慢死了
//下面这份代码处理找反向边的神仙操作就来了
edges[Tot] = Link {V, Cap, Cost, 0, Head[U]};
Head[U] = Tot++;
//正向加了一条偶数行的正向边后，又加了一条行数为奇数的反向边
//花费为负值，用来在取消流时使用。但反向边一开始时是没有容量的，即不能直接在这条边上加流
//只能取消这上面由于反向加边产生的流
//由于我们这样的建边方式，那么edges[i]这条边的反向边就是edges[i^1]，不解释，可好玩
edges[Tot] = Link {U, 0, -Cost, 0, Head[V]};
Head[V] = Tot++;
}
//可知我们的图总共分四层
//超级源点一层，
//有货的一层
//缺货的一层
//超级汇点一层
//我们使用广搜，必定是严格按照一层一层的搜索的，不解释
//那么我们怎么才能正确的进行增广呢？
//我们的最终目的是要找到最小费用的最大流
//那么我们是不是可以在找增广路径的时候使用贪心的思想，
//假如找到的每一条增广路径都是当前能找到的花费最小的增广路，那么我们的最终花费不就一定是最小的了吗
//因为如果我们加了一条不是当前最小花费的流，那么他必定会反向加边，
//那么我们在下一轮的搜索中必定会找到，这个不太聪明的流而反向取消他
//所以贪心的去搜索当前花费最小的流就好
//那么我们怎么找当前花费最小的路径呀，我们用Path来标记到当前节点，运输单位物资花费最小的点
//用Dis来保存到当前节点，运输单位物资花费最小的值
//当前点的花费一定是 所有上一层节点中的（Dis+到当前节点花费）的最小值。
//然后我们就相当于构建了一个已经在最小花费的集合的点集，和不在最小花费点集的一个点集
//然后使用当前这个点来优化那些不在当前最小花费点集的那些点。
//思想就是dijkstra的最短路径思想
//最终我们就找到了一条从超级源点，到超级汇点的最小单位花费的一条路径。
//之后进行增广就好啦
bool Spfa(int Start, int End)
{
memset(Dis, INF, sizeof(Dis));
memset(Vis, false, sizeof(Vis));
memset(Path, -1, sizeof(Path));
Dis[Start] = 0;
Vis[Start] = true;
std::queue Que;
while (!Que.empty())
{
Que.pop();
}
Que.push(Start);
while (!Que.empty())
{
int U = Que.front();
Que.pop();
Vis[U] = false;
for (int i = Head[U]; i != -1; i = edges[i].Next)
{
int V = edges[i].V;
if (edges[i].Cap > edges[i].Flow && Dis[V] > Dis[U] + edges[i].Cost)
{
Dis[V] = Dis[U] + edges[i].Cost;
Path[V] = i;
if (!Vis[V])
{
Vis[V] = true;
Que.push(V);
}
}
}
}
return Path[End] != -1;
}
//这个没啥好解释的嘛
//就是使用Spfa找到花费最小的那个路，进行增广就好
//让后正向减边，反向加边就好
//至于找反向边按个骚操作也解释过了
int MinCostMaxFlow(int Start, int End, long long &MinCost)
{
int MaxFlow = 0;
MinCost = 0;
while (Spfa(Start, End))
{
int Min = INF;
for (int i = Path[End]; i != -1; i = Path[edges[i ^ 1].V])
{
if (edges[i].Cap - edges[i].Flow < Min) {
Min = edges[i].Cap - edges[i].Flow;
}
}
for (int i = Path[End]; i != -1; i = Path[edges[i ^ 1].V]) {
edges[i].Flow += Min;
edges[i ^ 1].Flow -= Min;
MinCost += edges[i].Cost * Min;
}
MaxFlow += Min;
}
return MaxFlow;
}
int main(int argc, char *argv[])
{
while (~scanf("%d", &N))
{
Init();//head=-1 Tot=0
for (int i = 1; i <= N; ++i)
{
scanf("%d", &A[i]);
}
for (int i = 1; i <= N; ++i)
{
scanf("%d", &B[i]);
}
for(int i=1;i<=N;i++)
{
if(B[i]&&A[i])
{
int t=min(A[i],B[i]);
A[i]-=t;
B[i]-=t;
}
if(A[i])
AddEdge(0, i, A[i], 0);//初始化超级源点到a
if(B[i])
AddEdge(i, N + 1, B[i], 0);//初始化b到超级汇点
}
//添加题目给的费用路径
for (int i = 1, U, V, C; i < N; ++i)
{
scanf("%d%d%d", &U, &V, &C);
AddEdge(U, V, INF, C);
AddEdge(V, U, INF, C);
}
long long MinCost;
//计算最小费用最大流
MinCostMaxFlow(0, N + 1, MinCost);
printf("%lld
", MinCost);
}
return 0;
}
以上为教学部分下面看一道真题。。
飞行路线 Description
Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？
Input 数据的第一行有三个整数，n,m,k，分别表示城市数，航线数和免费乘坐次数。
第二行有两个整数，s,t，分别表示他们出行的起点城市编号和终点城市编号。(0<=s,t<n)
接下来有m行，每行三个整数，a,b,c，表示存在一种航线，能从城市a到达城市b，或从城市b到达城市a，价格为c。(0<=a,b<n,a与b不相等，0<=c<=1000)
Output 只有一行，包含一个整数，为最少花费。
Sample Input 1
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100 Sample Output 1
8 Hint
对于30%的数据,2<=n<=50,1<=m<=300,k=0;
对于50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1;
对于100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10.
他有k次机会来进行白嫖，那么我们什么时候进行白嫖赚的最多啊？？
不知道，所以要去搜索，想一下如果直接使用标记，我们当前白嫖了m次，剩k-m这种方式去搜索，那么我们也是可以做的呀。这样想下去应该是递归深搜？感觉可能能做。
也可以使用建模，把每一次白嫖都来到一个新的图，这样就是物理计数器了，感觉都一样。 题解：https://blog.csdn.net/qq_35416331/article/details/80366619
我去试试深搜。