UVa 820 Internet Bandwidth

题目描述给定一个包含n nn个节点的网络节点编号为1 11到n nn。每条连接有一个带宽容量双向相同。可能存在多条连接连接同一对节点。要求计算从源节点s ss到汇点t tt的最大数据传输速率即网络最大流。输入包含多个网络以n 0 n 0n0结束。输入格式每个网络描述第一行为整数n nn2 ≤ 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 0n0结束。输出格式对于每个网络输出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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXV110,INF1000000;constintUNLABELED-1,UNCHECKED0,CHECKED1;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));// 首先标记源点为已标号未检查顶点。queueintunchecked;unchecked.push(source);flags[source]flag{UNCHECKED,-1,INF};// 当汇点尚未被标记且队列非空时继续。while(flags[sink].statusUNLABELED!unchecked.empty()){// 取出位于队列首的顶点u。intuunchecked.front();unchecked.pop();// 检查与顶点u正向或反向连接的其他顶点v。for(intv1;vnodes;v){// 如果顶点v尚未被标号则予以标号。if(flags[v].statusUNLABELED){if(arcs[u][v].capacityINFarcs[u][v].flowarcs[u][v].capacity){flags[v].statusUNCHECKED,flags[v].parentu;flags[v].alphamin(flags[u].alpha,arcs[u][v].capacity-arcs[u][v].flow);unchecked.push(v);}elseif(arcs[v][u].capacityINFarcs[v][u].flow0){flags[v].statusUNCHECKED,flags[v].parent-u;flags[v].alphamin(flags[u].alpha,arcs[v][u].flow);unchecked.push(v);}}}// 顶点u已经标号且已经检查完毕。flags[u].statusCHECKED;}// 当标号过程未能到达汇点或者汇点的调整量为0表明已经不存在改进路。if(flags[sink].statusUNLABELED||flags[sink].alpha0)break;// 汇点有标号根据汇点的改进量沿着改进路对容量网络进行调整。intvsink,uabs(flags[v].parent),offsetflags[v].alpha;while(true){if(arcs[u][v].flowINF)arcs[u][v].flowoffset;elsearcs[v][u].flow-offset;// 调整到汇点退出。if(usource)break;vu,uabs(flags[u].parent);}}// 统计从源点流出的总流量。intmaxFlow0;for(intu1;unodes;u)if(arcs[source][u].flowINF)maxFlowarcs[source][u].flow;returnmaxFlow;}voidcreateGraph(){// 初始化有向弧。for(inti1;inodes;i)for(intj1;jnodes;j)arcs[i][j].capacityarcs[i][j].flowINF;cinsourcesinkconnections;intfrom,to,capacity;for(intc1;cconnections;c){cinfromtocapacity;if(arcs[from][to].flowINF){arcs[from][to].capacity0;arcs[from][to].flow0;arcs[to][from].capacity0;arcs[to][from].flow0;}arcs[from][to].capacitycapacity;arcs[to][from].capacitycapacity;}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;while(cinnodes,nodes0){createGraph();intmaxFlowfordFulkerson();coutNetwork cases\n;coutThe 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足够。注意多边累加容量输出格式要求每个网络后空行。该解法清晰高效是最大流问题的经典应用。