★ 输入文件:ugrid.in
输出文件:ugrid.out
简单对比
时间限制:1 s 内存限制:128 MB
- TYVJ八月月赛提高组第2题
- 测试点数目:5
- 测试点分值:20
- –内存限制:128M
- –时间限制:1s
【题目描述】
北冰洋有一座孤岛,多年来一直没电。近日,令岛民们振奋的消息传来:S国的专家要为他们修建电网!!!
孤 岛上共有N个村庄,发电站要建在第K个村庄中。S国的专家要在N个村庄间修建M条输电线路,但由于地理原因,M条线路无法保证每个村庄都与第K个村庄(建 有发电站)直接相连,同样,也不一定能保证每个村庄都与第K个村庄间接相连(假设A与B直接相连,B与C直接相连,那么A与C间接相连)。
然而,由于S国的专家智商实在太“高”了,以至于设计出了许多冗余线路。现给出第i条线路两个端点Ui,Vi(分别表示线路连接的两个村庄,Ui!=Vi)和长度Li,请你帮岛民算一下:如果电网可以覆盖全岛,最少需要多长的电线;若不能,有多少个村庄无电可用。
注意:0<=冗余线路数目<m;部分数据有重边。电网可双向导电。
【输入格式】
第一行:N M K
接下来M行:Ui Vi Li
具体含义见题目描述
【输出格式】
如果电网可以覆盖全岛,输出最少需要的电线长度;
若不能,输出无电可用的村庄的个数。
【样例输入】
【样例1】
5 5 1
1 2 1
2 3 1
3 4 1
4 5 1
5 1 1【样例2】
5 5 1
1 2 1
1 2 2
1 2 3
3 4 1
5 4 2
【样例输出】
【样例1】
4【样例2】
3
【提示】
样例解释:
对于样例一,电网可以覆盖全岛,最短长度为4;
对于样例二,电网无法覆盖3,4,5这3个村庄。
数据范围:
对于20%的数据,有1<m,n<=10;
对于60%的数据,有1<m,n<=1000;
对于100%的数据,有1<m,n<=200000,0<li<=1e+7;
对于40%的数据,电网无法覆盖全岛。
【来源】
From tbcaaa8 http://www.tyvj.cn/Problem_Show.aspx?id=1591
kruskal
(rank1 蛤蛤)
#include <algorithm>
#include <cstdio>
#define N 200005
using namespace std;
struct Edge
{
int x,y,z;
bool operator<(Edge a)const
{
return z<a.z;
}
}e[N];
int n,m,k,cnt,fa[N];
int find_(int x) {return fa[x]==x?x:fa[x]=find_(fa[x]);}
int Main()
{
freopen("ugrid.in","r",stdin);
freopen("ugrid.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;++i) fa[i]=i;
for(int x,y,z;m--;)
{
scanf("%d%d%d",&x,&y,&z);
e[++cnt]=(Edge){x,y,z};
}
sort(e+,e++cnt);
int num=;
long long sum=;
for(int i=;i<=cnt;++i)
{
int fx=find_(e[i].x),fy=find_(e[i].y);
if(fx==fy) continue;
fa[fy]=fx;
num++;
sum+=(long long)e[i].z;
if(num==n-) break;
}
num=,k=find_(k);
for(int i=;i<=n;++i) if(find_(i)!=k) num++;
if(num) printf("%d\n",num);
else printf("%lld\n",sum);
return ;
}
int sb=Main();
int main(int argc,char *argv[]){;}