uva 820 - Internet Bandwidth(최대 유입 문항)
Internet Bandwidth
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
제목:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=761
분석: 그림을 작성하여 직접 최대 흐름을 만들면 됩니다. 답안 하나하나 뒤에 빈 줄=, 그래요. 저는 정말 더 이상 약해질 수 없어요.
코드:#include<cstdio>
#include<iostream>
using namespace std;
const int mm=222222;
const int mn=111;
const int oo=1e9;
int src,dest,node,edge;
int ver[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
void addedge(int u,int v,int c)
{
ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
ver[edge]=u,flow[edge]=c,next[edge]=head[v],head[v]=edge++;
}
int Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0; i<node; ++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0; l<r; ++l)
for(i=head[u=q[l]]; i>=0; i=next[i])
if(flow[i]&&dis[v=ver[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp; i>=0; i=next[i])
if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}
return 0;
}
int Dinic_flow()
{
int i,delta,ret=0;
while(Dinic_bfs())
{
for(i=0; i<node; ++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
int main()
{
int i,j,n,m,c,t=0;
while(scanf("%d",&n),n)
{
scanf("%d%d%d",&i,&j,&m);
prepare(n+1,i,j);
while(m--)
{
scanf("%d%d%d",&i,&j,&c);
addedge(i,j,c);
}
printf("Network %d
The bandwidth is %d.
",++t,Dinic_flow());
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)
ios에서 루아 함수 호출 및 전참 방법
lua 코드:
출력 결과:
lua 호출 C++ 방법:
add 함수:
lua 코드:
출력 결과:
함수를 호출합니다.
함수를 호출하려면 다음 협의를 따르십시오.
우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
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.
#include<cstdio>
#include<iostream>
using namespace std;
const int mm=222222;
const int mn=111;
const int oo=1e9;
int src,dest,node,edge;
int ver[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
void addedge(int u,int v,int c)
{
ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
ver[edge]=u,flow[edge]=c,next[edge]=head[v],head[v]=edge++;
}
int Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0; i<node; ++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0; l<r; ++l)
for(i=head[u=q[l]]; i>=0; i=next[i])
if(flow[i]&&dis[v=ver[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp; i>=0; i=next[i])
if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}
return 0;
}
int Dinic_flow()
{
int i,delta,ret=0;
while(Dinic_bfs())
{
for(i=0; i<node; ++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
int main()
{
int i,j,n,m,c,t=0;
while(scanf("%d",&n),n)
{
scanf("%d%d%d",&i,&j,&m);
prepare(n+1,i,j);
while(m--)
{
scanf("%d%d%d",&i,&j,&c);
addedge(i,j,c);
}
printf("Network %d
The bandwidth is %d.
",++t,Dinic_flow());
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.