解题报告 之 UVA820 Internet Bandwidth
解题报告 之 UVA820 Internet Bandwidth
Description
On the Internet, machines (nodes) are richly interconnected, and many paths may exist between a given pair of nodes. The total message-carrying capacity (bandwidth) between two given nodes is the maximal amount of data per unit time that can be transmitted from one node to the other. Using a technique called packet switching, this data can be transmitted along several paths at the same time.
For example, the following figure shows a network with four nodes (shown as circles), with a total of five connections among them. Every connection is labeled with a bandwidth that represents its data-carrying capacity per unit time.
In our example, the bandwidth between node 1 and node 4 is 25, which might be thought of as the sum of the bandwidths 10 along the path 1-2-4, 10 along the path 1-3-4, and 5 along the path 1-2-3-4. No other combination of paths between nodes 1 and 4 provides a larger bandwidth.
You must write a program that computes the bandwidth between two given nodes in a network, given the individual bandwidths of all the connections in the network. In this problem, assume that the bandwidth of a connection is always the same in both directions (which is not necessarily true in the real world).
Input
The input file contains descriptions of several networks. Every description starts with a line containing a single integer n (2 ≤n ≤100), which is the number of nodes in the network. The nodes are numbered from 1 to n. The next line contains three numbers s, t, and c. The numbers s and t are the source and destination nodes, and the number c is the total number of connections in the network. Following this are c lines describing the connections. Each of these lines contains three integers: the first two are the numbers of the connected nodes, and the third number is the bandwidth of the connection. The bandwidth is a non-negative number not greater than 1000.
There might be more than one connection between a pair of nodes, but a node cannot be connected to itself. All connections are bi-directional, i.e. data can be transmitted in both directions along a connection, but the sum of the amount of data transmitted in both directions must be less than the bandwidth.
A line containing the number 0 follows the last network description, and terminates the input.
Output
For each network description, first print the number of the network. Then print the total bandwidth between the source node s and the destination node t, following the format of the sample output. Print a blank line after each test case.
| Sample Input | Output for the Sample Input |
|---|---|
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. |
ACM World Finals 2000, Problem E
题目大意：有一个计算机网络，输入节点数n，输入网络流源点和汇点src，des，再输入双向边数m。给出m条边的负载，求最大流。
分析：裸的最大流，连背景都不包装了，于是乎直接敲了模板跑最大流即可。注意唯一的坑点在于输出要多一行空行，没看到就一直WA把。于是乎解题报告至此结束啦。
上代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAXM = 160000;
const int MAXN = 400;
const int INF = 0x3f3f3f3f;
struct Edge
{
int to, cap, next;
};
Edge edge[MAXM];
int level[MAXN];
int head[MAXN];
int src, des, cnt;
void addedge( int from, int to, int cap )
{
edge[cnt].to = to;
edge[cnt].cap = cap;
edge[cnt].next = head[from];
head[from] = cnt++;
swap( from, to );
edge[cnt].to = to;
edge[cnt].cap = cap;
edge[cnt].next = head[from];
head[from] = cnt++;
}
int bfs()
{
memset( level, -1, sizeof level );
queue<int>q;
while (!q.empty())
q.pop();
level[src] = 0;
q.push( src );
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].cap > 0 && level[v] == -1)
{
level[v] = level[u] + 1;
q.push( v );
}
}
}
return level[des] != -1;
}
int dfs( int u, int f )
{
if (u == des) return f;
int tem;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].cap>0&&level[v] == level[u] + 1)
{
tem = dfs( v, min( f, edge[i].cap ) );
if (tem > 0)
{
edge[i].cap -= tem;
edge[i^1].cap += tem;
return tem;
}
}
}
level[u] = -1;
return 0;
}
int Dinic()
{
int ans = 0, tem;
while (bfs())
{
while ((tem = dfs( src, INF )) > 0)
{
ans += tem;
}
}
return ans;
}
int main()
{
int n, m;
int kase = 1;
while (cin >> n&&n)
{
memset( head, -1, sizeof head );
cnt = 0;
cin >> src >> des >> m;
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
addedge( a, b, c );
}
printf( "Network %d\nThe bandwidth is %d.\n\n",kase++, Dinic() );
}
return 0;
}
啦啦啦啦啦啦啦，好有诚意的一道题。。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
