ACTime

let's start
随笔 - 10, 文章 - 22, 评论 - 2, 引用 - 0
数据加载中……

POJ 1797 Heavy Transportation(最大树最小边变形)

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1797
题目描述:求从指定起点到指定终点每条可能路径上各段边的最小值
注意事项:有向图/无向图
提交情况:3次Runtime Error,是最开始尝试用Kruskal时间接排序的数组r大小只开了MAXN个;3次WA的主要原因是无向图按照有向图做的。用邻接表存储图时一定要注意有向图和无向图的问题,已经出错好几次了。
心得体会:本道题实际是按照Prim求最大生成树的思路,逐条添加边;在添加的过程中,注意从1点出发,在遇到n时,即使最大生成树仍没有构造完,也可以从函数中返回了。最开始以为是简单的生成树问题,所有用Kruskal来作,遇到起点和终点都访问过就退出,但此时,构造的生成树可能根本就没有连接,而Prim在构造的初始就是从一棵树开始拓展的,不会出现这个问题。需要对每个具体的算法有更深入的理解。
 1 #include<queue>
 2 #include<stdio.h>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 #define MAXN 1010 
 7 #define MAXM 1000010 
 8 
 9 struct Edge
10 {
11     int start;
12     int end;
13     int weight;
14 
15     bool operator>(const Edge &e) const
16     {
17         return weight<e.weight;
18     }
19 };
20 
21 Edge edge[2*MAXM];
22 int visited[MAXN];
23 int first[MAXN];
24 int next[2*MAXM];
25 
26 int Prim(int n)
27 {
28     memset(visited,0,sizeof(visited));
29     int result = 10000000;
30     priority_queue<Edge,vector<Edge>,greater<Edge> > pq;
31     for(int e=first[1];e!=-1;e=next[e])
32     {
33         pq.push(edge[e]);
34     }
35     visited[1]=1;
36    
37     while(!pq.empty())
38     {
39         int start = pq.top().start;
40         int end = pq.top().end;
41         int weight = pq.top().weight;
42         pq.pop();
43 
44         if(visited[end]==1)
45             continue;
46         visited[end] = 1;
47         
48         if(weight<result)
49             result = weight;
50         if(end==n)
51            break;
52         for(int e=first[end];e!=-1;e=next[e])
53         {
54             if(visited[edge[e].end]==0)
55             {
56                 pq.push(edge[e]);
57             }
58         }
59     }
60     return result;
61 }
62 
63 int main()
64 {
65     int snum;
66     scanf("%d",&snum);
67     for(int i=1;i<=snum;i++)
68     {
69         int n,m,start,end,weight;
70         scanf("%d%d",&n,&m);
71         
72         memset(first,-1,sizeof(first));       
73         for(int j=0;j<2*m;j+=2)
74         {
75             scanf("%d%d%d",&start,&end,&weight);
76             
77             edge[j].start = start;
78             edge[j].end = end;
79             edge[j].weight = weight;
80 
81             edge[j+1].start = end;
82             edge[j+1].end = start;
83             edge[j+1].weight = weight;
84 
85             next[j] = first[start];
86             first[start] = j; 
87 
88             next[j+1= first[end];
89             first[end] = j+1;
90               
91         }
92 
93         int result = Prim(n);
94         printf("Scenario #%d:\n",i);
95         printf("%d\n\n",result);
96     }
97 }

posted on 2010-01-01 14:24 ACTime 阅读(846) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理