首页 > 代码库 > hdu 3371 Connect the Cities (最小生成树Prim)
hdu 3371 Connect the Cities (最小生成树Prim)
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3371
题目不难 稍微注意一下 要把已经建好的城市之间的花费定义为0,在用普通Prim算法就可以了;我没有用克鲁斯卡尔算法(Kruskal‘s algorithm),因为这题数据比较大,而且要处理大量的数据使它为0,怕超时T^T。。。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 7 #define inf 999999 8 9 int map[505][505],node[505],n,vis[505];10 int dd[505],sum;11 12 int Prim()13 {14 int tm=1;15 node[tm]=0;16 //vis[tm]=1;17 for(int k=1;k<=n;k++)18 {19 int minn=inf;20 for(int i=1;i<=n;i++)21 if(!vis[i]&&minn>node[i])22 {23 tm=i;24 minn=node[i];25 }26 vis[tm]=1;27 if(minn==inf)28 return 0;29 30 sum+=minn;31 32 for(int i=1;i<=n;i++)33 {34 if(!vis[i]&&node[i]>map[tm][i])35 node[i]=map[tm][i];36 }37 }38 return 1;39 }40 41 int main()42 {43 int T;44 scanf("%d",&T);45 while(T--)46 {47 int m,k;48 scanf("%d%d%d",&n,&m,&k);49 for(int i=1;i<=n;i++)50 {51 node[i]=inf;vis[i]=0;52 for(int j=1;j<=n;j++)53 map[i][j]=inf;54 }55 while(m--)56 {57 int a,b,d;58 scanf("%d%d%d",&a,&b,&d);59 if(map[a][b]>d)60 map[a][b]=map[b][a]=d;61 }62 while(k--)63 {64 int t;65 scanf("%d",&t);66 for(int i=1;i<=t;i++)67 {68 scanf("%d",&dd[i]);69 }70 for(int i=1;i<=t;i++)71 {72 for(int j=i+1;j<=t;j++)73 map[dd[i]][dd[j]]=map[dd[j]][dd[i]]=0;74 }75 }76 sum=0;77 int flag=Prim();78 if(flag==0)79 printf("-1\n");80 else81 printf("%d\n",sum);82 }83 return 0;84 }
hdu 3371 Connect the Cities (最小生成树Prim)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。