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