题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=3371

题目大意:

给n个城市,m条路,k组已知路,求最小费用联通所有城市;

解题思路:

kruskal求MST,这道题目有毒,很容易超时,改了一下并查集才过,而且同一个代码有时过又是超时

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = + ;
const int INF = 0x3f3f3f3f;
int p[maxn];
int tot;
void init()
{
for(int i = ; i < maxn; i++)p[i] = i;
}
int f(int x)
{
return x == p[x] ? x : p[x] = f(p[x]);
}
void Union(int x, int y)
{
x = f(x);
y = f(y);
if(x != y)
{
p[x] = y;//这里改成p[y] = x;有时过,有时会超时
tot--;//不联通的数目减一
}
}
struct edge
{
int u, v, w;
bool operator < (const edge& a)
{
return w < a.w;
}
}a[maxn * maxn];
int main()
{
int T, n, m, k, t, x, y;
scanf("%d", &T);
while(T--)
{
init();
scanf("%d%d%d", &n, &m, &k);
tot = n - ;//最开始,不连通块数目为n-1
for(int i = ; i <= m; i++)
{
scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);
}
sort(a + , a + + m);
while(k--)
{
scanf("%d%d", &t, &x);
t--;
while(t--)
{
scanf("%d", &y);
Union(x, y);
}
}
int ans = ;/*
for(int i = 1; i <= n; i++)cout<<p[i]<<" ";
cout<<endl;*/
for(int i = ; i <= m; i++)
{
int x = a[i].u;
int y = a[i].v;
x = f(x), y = f(y);
if(x != y)
{
p[x] = y;
tot--;//不连通数目减一
ans += a[i].w;
}
}
if(tot == )//全部连通
printf("%d\n", ans);
else
printf("-1\n");
}
return ;
}

最新文章

  1. (转载)The One Sign You Will Be Rich-(by Brian de Haaff Founder and CEO Aha! -- world&#39;s #1 product roadmap software)
  2. 关于QCon2015感想与反思
  3. WinForm------TreeList属性介绍
  4. javascript语法详解
  5. a mystrious max subquence sum
  6. WCF note1
  7. 微信公众平台--网页授权获取用户基本信息(snsapi_userinfo方式)
  8. 关于KEIL编译报错和警告问题
  9. PHP 设计模式(一)
  10. Shell 示例:利用 $RANDOM 产生随机整数
  11. Nginx Linux安装与部署
  12. [POI2011]Rotacje na drzewie (2)/[BZOJ3702]二叉树
  13. localstorage 和 sessionstorage 是什么?区别是什么?
  14. HDU 4391 Paint The Wall(分块的区间维护)
  15. RHEL-server-7.0-Linux-centos安装过程
  16. Ansible中playbook的变量
  17. 根据数据库的表生成项目,项目变为hibernate项目(实际开发中常用)
  18. TimescaleDB 简单试用
  19. 【常见CPU架构对比】维基百科
  20. SQL Server计算列

热门文章

  1. svn图标修复
  2. luogu3224 永无乡(动态开点,权值线段树合并)
  3. Kubernetes基本概念之Name和NameSpace
  4. 微信小程序在sublime开发代码高亮显示
  5. nodejs安装及使用步骤详解
  6. C# Repeater 嵌套
  7. JavaScript刷新页面,不重复提交
  8. 我在B站学习 Javascript入门教程 基础
  9. Restful 3 -- 序列化组件(GET/PUT/DELETE接口设计)、视图优化组件
  10. LogAspect