03:丛林中的路
2018-06-18 04:00:55来源:未知 阅读 ()
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
热带岛屿Lagrishan的首领现在面临一个问题:几年前,一批外援资金被用于维护村落之间的道路,但日益繁茂的丛林无情的侵蚀着村民的道路,导致道路维修开销巨大,长老会不得不放弃部分道路的维护。上图左侧图显示的是正在使用道路的简图以及每条路每个月的维修费用(单位为aacms)。现在长老会需要提出一种方案,即需要保证村落之间都可以互相到达,又要将每个月的道路维修费用控制在最小。村子编号为从A到I。上图右侧显示的方案最小维修开销为216 aacms每月。
- 输入
- 输入包含1~100个数据集,最后一行为0.每个数据集第一行为村落数目n, 1 < n < 27,依次用字母表的前n个字母标记。接下来有n-1行,每行的第一个数据便是按字母顺序排列的村子编号(不包括最后一个村庄)。每个村庄后面的数据k代表该村庄通往编号在其之后的村庄的道路数目,如A 2 B 12 I 25,代表A村庄有2个编号在A之后的村庄和其相连。若k大于0,k后面会依次给出这k个村庄的编号以及各自到起始村庄的道路维修费用,如A 2 B 12 I 25,代表A和B之间道路维修费用为12, A和I之间道路维修费用为25(维修费用为不超过100的正整数).路的总数目不超过75条,每个村庄到其他村庄不会有超过15条路(包括编号在其之前和之后的)。
- 输出
- 每个数据集有一个输出:针对解决方案每个月维修道路的小费用。
提示:蛮力算法虽能找出解决方案,但将会超出时间限制。 - 样例输入
-
9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0
- 样例输出
-
216 30
kruskal最小生成树裸题,不知道题目中说的暴力是什么算法,,,,1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=50001; 7 void read(int &n) 8 { 9 char c='+';int x=0;bool flag=0; 10 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 11 while(c>='0'&&c<='9') 12 x=(x<<1)+(x<<3)+c-48,c=getchar(); 13 flag==1?n=-x:n=x; 14 } 15 int fa[MAXN]; 16 int find(int x) 17 { 18 if(fa[x]==x) 19 return fa[x]; 20 return fa[x]=find(fa[x]); 21 } 22 void unionn(int x,int y) 23 { 24 int fx=find(x); 25 int fy=find(y); 26 fa[fx]=fy; 27 } 28 int idx(char n) 29 {return (n-64);} 30 int n; 31 struct node 32 { 33 int u,v,w,nxt; 34 }edge[MAXN]; 35 int head[MAXN]; 36 int num=1; 37 bool vis[MAXN]; 38 int add_edge(int x,int y,int z) 39 { 40 edge[num].u=x; 41 edge[num].v=y; 42 edge[num].w=z; 43 edge[num].nxt=head[x]; 44 head[x]=num++; 45 } 46 int comp(const node &a,const node &b) 47 { 48 return a.w<b.w; 49 } 50 void kruskal() 51 { 52 int ans=0; 53 int tot=0; 54 sort(edge+1,edge+num,comp); 55 for(int i=1;i<num;i++) 56 { 57 if(find(edge[i].u)!=find(edge[i].v)) 58 { 59 unionn(edge[i].u,edge[i].v); 60 ans+=edge[i].w; 61 } 62 if(tot==n-1) 63 break; 64 } 65 printf("%d\n",ans); 66 } 67 void pre() 68 { 69 num=1; 70 for(int i=1;i<=n;i++) 71 fa[i]=i; 72 } 73 int main() 74 { 75 while((scanf("%d",&n))) 76 { 77 pre(); 78 if(n==0)break; 79 for(int i=1;i<=n-1;i++) 80 { 81 char meiyong;int num; 82 cin>>meiyong; 83 read(num); 84 for(int j=1;j<=num;j++) 85 { 86 char will;int p; 87 cin>>will;read(p); 88 add_edge(i,idx(will),p); 89 } 90 } 91 kruskal(); 92 } 93 return 0; 94 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C/C++ 定义与声明详解(转)
下一篇:C语言-常量指针与指针常量
- 测量C++程序运行时间 2020-04-17
- Emergency Evacuation(最短下车时间)———(思维) 2020-04-11
- linux环境下的时间编程 2020-03-27
- C++常见编程--获取当前系统时间 2020-02-25
- c++-字符串和时间操作 2019-12-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash