首页 > 代码库 > NOJ1056地道——最小生成树+贪心算法
NOJ1056地道——最小生成树+贪心算法
地道
Total Submit:289 Accepted:60
Description
话说南京的城市规划一般一般,各个大学分布极不合理,难于沟通。
我们夜猫族打算用一种常人难以想象的方式建立大学通道:用地道使得所有大学都相通。
但地道的造价不菲,而大学生是贫困群体,所以我们希望用尽量小的代价。
已知建设一条地道的费用和地道的距离成正比。其关系是,一个单位的距离需要的花费是7个ACM币,在ACM世界里货币的换算方法简单极了,29个ACM币等于一个DS币,17个DS币等于一个算法币。(ACM币单位为ac,DS币单位为ds,算法币单位为al)
但是学校太多了,而且有些学校不能直接连接(比如,跨湖或跨江地道太难建设了)。需要聪明的你的帮助。
Input
第一行包含两个整数N,M。N表示学校总数(1≤N≤100),M表示所有能直接连接的学校的数量(1<=M<=N*(N-1)/2)。
以下M行,每行三个正整数,第一个数和第二个数为学校编号,第三个为这两个学校间的距离L(0<=L<=10000)。
Output
若干带单位(ac,ds或al)的正整数,数字要尽可能小,单位复杂一点无妨(即把单位(ac,ds,al)转换得尽可能大,能用大单位表示尽量用大单位)数与单位间无空格。
Sample Input
4 6
1 2 4
1 3 9
1 4 21
2 3 8
2 4 17
3 4 16
Sample Output
6ds22ac
Source
wwm
分析:此题需要求连通所有节点的边的最小值。摸索出了最小生成树。一开始在纠结Dijkstra算法求最短路。注意:Dijkstra算法是单源最短路径算法,适用于计算一个节点到其他所有节点的最短路径。这里显然不适用。
扩展:
一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。
数据结构书中有介绍过,就是不断的加入点,每次都是最短的边。细细体会算法!
于是用Prim算法求最小生成树:
bool vis[101]; int dis[101]; bool prim() { memset(vis, false, sizeof(vis)); for(int i=1;i<=n;i++) dis[i] = INF; ans =0; dis[1] = 0; for(int i=1;i<=n;i++) { int tmp = INF, k =0; for(int j=1;j<=n;j++) { if(! vis[j] && dis[j] < tmp) { tmp = dis[j]; k = j; } } if(tmp == INF) return false; vis[k] = true; ans += tmp; for(int j=1;j<=n;j++) { if(! vis[j] && dis[j] > a[k][j]) dis[j] = a[k][j]; } } return true; }之后就是用贪心算法求出各种B有多少。(贪心一点都高端好么?)这里的贪心我写的复杂了,其实直接整除就行~又蠢了= =
输出有一些小问题,一开始分情况判断输出,简直蠢 T_T
另外,ACM币一定会输出。
完整代码:
#include<iostream> #include<algorithm> using namespace std; #define INF 1000000000 //地道 int n, m, a[101][101], ans; bool vis[101]; int dis[101]; bool prim() { memset(vis, false, sizeof(vis)); for(int i=1;i<=n;i++) dis[i] = INF; ans =0; dis[1] = 0; for(int i=1;i<=n;i++) { int tmp = INF, k =0; for(int j=1;j<=n;j++) { if(! vis[j] && dis[j] < tmp) { tmp = dis[j]; k = j; } } if(tmp == INF) return false; vis[k] = true; ans += tmp; for(int j=1;j<=n;j++) { if(! vis[j] && dis[j] > a[k][j]) dis[j] = a[k][j]; } } return true; } int main() { int tmp_a, tmp_b, tmp_c, ac = 0, ds = 0, al = 0; // 学校从编号1开始 ans = 0; memset(a, 0, sizeof(a)); scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d%d",&tmp_a,&tmp_b,&tmp_c); a[tmp_a][tmp_b] = tmp_c; a[tmp_b][tmp_a] = tmp_c; } prim(); ans *= 7; int tmp = ans; while(ans >= 29) { ans -=29; ds ++; } ac = tmp - ds*29; tmp = ds; while(ds >= 17) { ds -= 17; al ++; } ds = tmp - al*17; /* if(al == 0) // wrong! { if(ds == 0 && ac != 0) printf("%dds\n",ds); else if(ds != 0 && ac != 0) printf("%dds%dac\n",ds,ac); else // ds != 0 && ac == 0 printf("%dac\n",ac); } else { if(ds == 0 && ac == 0) printf("%dal\n",al); else if(ds !=0 && ac == 0) printf("%dal%dac\n",al,ac); else if(ds == 0 && ac != 0) printf("%dal%dds\n",al,ds); else printf("%dal%dsa%dac\n",al,ds,ac); } */ if(al != 0) printf("%dal",al); if(ds != 0) printf("%dds",ds); printf("%dac\n",ac); return 0; }