企业官网建设流程全解析

题目描述

给定一个包含n nn个节点的网络，节点编号为1 11到n nn。每条连接有一个带宽容量（双向相同）。可能存在多条连接连接同一对节点。要求计算从源节点s ss到汇点t tt的最大数据传输速率（即网络最大流）。输入包含多个网络，以n = 0 n = 0n=0结束。

输入格式

每个网络描述第一行为整数n nn（2 ≤ n ≤ 100 2 \le n \le 1002≤n≤100）。第二行为三个整数s , t , c s, t, cs,t,c，分别表示源节点、汇点、连接数。随后c cc行，每行三个整数u , v , w u, v, wu,v,w，表示节点u uu和v vv之间的双向连接，带宽为w ww。输入以n = 0 n = 0n=0结束。

输出格式

对于每个网络，输出：

Network k The bandwidth is maxFlow.

每个网络输出后跟一个空行。

样例输入

4 1 4 5 1 2 20 1 3 10 2 3 5 2 4 10 3 4 20 0

样例输出

Network 1 The bandwidth is 25.

题目分析

求有向/无向网络的最大流。由于连接是双向的，但同一时刻两个方向的总流量不能超过带宽。可将每条无向边视为两条有向边，每条容量为w ww，但这样会允许两个方向同时满流，违反约束。正确建模是：将每条无向边替换为两条方向相反的有向边，但它们的流量之和不能超过w ww。这可以通过在残量网络中使用普通有向边实现：初始时，两条方向相反的弧容量均为w ww，在Ford-Fulkerson \texttt{Ford-Fulkerson}Ford-Fulkerson算法中，正向弧的流量增加会使反向弧的剩余容量减少，自动限制了双向总流量不超过w ww。因此，直接添加两条容量为w ww的有向弧即可。

解题思路

使用Ford-Fulkerson \texttt{Ford-Fulkerson}Ford-Fulkerson算法（或Edmonds-Karp \texttt{Edmonds-Karp}Edmonds-Karp）求解最大流。实现步骤：

步骤1 \texttt{1}1. 初始化邻接矩阵arcs [ u ] [ v ] \textit{arcs}[u][v]arcs[u][v]，存储容量capacity \textit{capacity}capacity和当前流量flow \textit{flow}flow。若有多条边连接同一对节点，容量累加。

步骤2 \texttt{2}2. 每次迭代，使用广度优先搜索（BFS \texttt{BFS}BFS）在残量网络中寻找从s ss到t tt的一条增广路径。残量网络中，正向边剩余容量为capacity − flow \textit{capacity} - \textit{flow}capacity−flow，反向边剩余容量为flow \textit{flow}flow（用于撤销流量）。标记每个节点的前驱节点和路径上的最小剩余容量。

步骤3 \texttt{3}3. 若无法到达t tt，则算法结束。否则，沿增广路径更新每条边的流量（正向边增加，反向边减少）。

步骤4 \texttt{4}4. 统计从s ss流出的总流量作为最大流。

由于n ≤ 100 n \le 100n≤100，边数有限，BFS \texttt{BFS}BFS标号法可高效运行。

代码实现

// Internet Bandwidth// UVa ID: 820// Verdict: Accepted// Submission Date: 2016-12-02// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXV=110,INF=1000000;constintUNLABELED=-1,UNCHECKED=0,CHECKED=1;structarc{intcapacity,flow;};structflag{intstatus,parent,alpha;};arc arcs[MAXV][MAXV];flag flags[MAXV];intsource,sink,nodes,connections;intfordFulkerson(){// 反复进行标号过程直到不存在改进路。while(true){// 初始化变量。memset(flags,-1,sizeof(flags));// 首先标记源点为已标号未检查顶点。queue<int>unchecked;unchecked.push(source);flags[source]=flag{UNCHECKED,-1,INF};// 当汇点尚未被标记且队列非空时继续。while(flags[sink].status==UNLABELED&&!unchecked.empty()){// 取出位于队列首的顶点u。intu=unchecked.front();unchecked.pop();// 检查与顶点u正向或反向连接的其他顶点v。for(intv=1;v<=nodes;v++){// 如果顶点v尚未被标号则予以标号。if(flags[v].status==UNLABELED){if(arcs[u][v].capacity<INF&&arcs[u][v].flow<arcs[u][v].capacity){flags[v].status=UNCHECKED,flags[v].parent=u;flags[v].alpha=min(flags[u].alpha,arcs[u][v].capacity-arcs[u][v].flow);unchecked.push(v);}elseif(arcs[v][u].capacity<INF&&arcs[v][u].flow>0){flags[v].status=UNCHECKED,flags[v].parent=-u;flags[v].alpha=min(flags[u].alpha,arcs[v][u].flow);unchecked.push(v);}}}// 顶点u已经标号且已经检查完毕。flags[u].status=CHECKED;}// 当标号过程未能到达汇点或者汇点的调整量为0，表明已经不存在改进路。if(flags[sink].status==UNLABELED||flags[sink].alpha==0)break;// 汇点有标号，根据汇点的改进量沿着改进路对容量网络进行调整。intv=sink,u=abs(flags[v].parent),offset=flags[v].alpha;while(true){if(arcs[u][v].flow<INF)arcs[u][v].flow+=offset;elsearcs[v][u].flow-=offset;// 调整到汇点，退出。if(u==source)break;v=u,u=abs(flags[u].parent);}}// 统计从源点流出的总流量。intmaxFlow=0;for(intu=1;u<=nodes;u++)if(arcs[source][u].flow<INF)maxFlow+=arcs[source][u].flow;returnmaxFlow;}voidcreateGraph(){// 初始化有向弧。for(inti=1;i<=nodes;i++)for(intj=1;j<=nodes;j++)arcs[i][j].capacity=arcs[i][j].flow=INF;cin>>source>>sink>>connections;intfrom,to,capacity;for(intc=1;c<=connections;c++){cin>>from>>to>>capacity;if(arcs[from][to].flow==INF){arcs[from][to].capacity=0;arcs[from][to].flow=0;arcs[to][from].capacity=0;arcs[to][from].flow=0;}arcs[from][to].capacity+=capacity;arcs[to][from].capacity+=capacity;}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0;while(cin>>nodes,nodes>0){createGraph();intmaxFlow=fordFulkerson();cout<<"Network "<<++cases<<'\n';cout<<"The bandwidth is "<<maxFlow<<".\n\n";}return0;}

总结

本题通过Ford-Fulkerson \texttt{Ford-Fulkerson}Ford-Fulkerson算法求解网络最大流。双向边处理为两条方向相反的有向边，容量相同，通过残量网络自动维持总流量不超过容量。算法使用BFS \texttt{BFS}BFS寻找增广路径（即Edmonds-Karp \texttt{Edmonds-Karp}Edmonds-Karp实现），复杂度O ( V E 2 ) O(V E^2)O(VE2)，对于V ≤ 100 V \le 100V≤100足够。注意多边累加容量，输出格式要求每个网络后空行。该解法清晰高效，是最大流问题的经典应用。