AOJ--The Max Weight--Floyd Folyd算法变形,把求最短路径的和改为求最大载重量的问题

The Max Weight
Time Limit: 1000 ms   Memory Limit: 64 MB
Total Submission: 36   Accepted: 4
Description
There a lot of bridges connect different positions in Venice,but they can't carry too much weigh,so each of them has a limit which can be described as an interger.A man wants to carry some goods from positon 1 to n.Help him find how much can he carry.

Input
There are T cases.
For each case,the number of positions ( 1 < = n < = 100) and number m of bridges are exhibited on the first line.The following m lines contain triples of integers specifying start and end positions of the bridge and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one bridge between each pair of crossings.

Output
The output for every scenario begins with a line containing "Case #i:", where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that the man can transport. Terminate the output for the scenario with a blank line.

Sampel Input
1
3 3
1 2 3
1 3 4
2 3 5 

Sample Output
Case #1:[EOL]
4[EOF]

题意:
n个点,有些点间有桥,桥上有最大承重量,问你从1到n可以最大携带的物品的重量。
题解: 
 Folyd算法变形,把求最短路径的和改为求最大载重量的问题,关键是dis[i][j]=dis[i][j]>dis[i][k]+dis[k][j]?dis[i][j]>dis[i][k]+dis[k][j]?:dis[i][j];换成dis[i][j]=max(dis[i][j],min(dis[i][k],dis[k][j]));
 1#include<iostream>
 2#include<cmath>
 3#include<string.h>
 4using namespace std;
 5long long dis[105][105];
 6 
 8void Floyd(int n)
 9{
10     for(int k=1; k<=n; k++)
11     for(int i=1; i<=n; i++)
12     for(int j=1; j<=n; j++)
13     {
14       if(i!=k&&j!=k&&dis[i][k]&&dis[k][j])
15         dis[i][j]=max(dis[i][j],min(dis[i][k],dis[k][j]));
16     }

17}

18
19int main()
20{
21    int t,i,j,m,n;
22    cin>>t;
23    for(int k=1; k<=t; k++)
24    {
25      cin>>n>>m;
26      memset(dis,0,sizeof (dis));
27      i=1;
28      for(int s,e,w; i<=m; i++)
29      {
30        cin>>s>>e>>w;
31        dis[s][e]=dis[e][s]=w;
32      }

33      
34      Floyd(n);
35      
36     cout<<"Case #"<<k<<':'<<endl<<dis[1][n]<<endl<<endl;
37    }

38    return 0;
39}

posted on 2010-05-29 22:03 田兵 阅读(1239) 评论(0)  编辑 收藏 引用 所属分类: 图论题


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年5月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜