COGS——T 1215. [Tyvj Aug11] 冗余电网

http://www.cogs.pro/cogs/problem/problem.php?pid=1215

★ 输入文件：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】
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

并查集判断是否在同一个连通块、最小生成树找ans

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 const int N(2100000);
 7 int n,m,k,fa[N];
 8 struct Edge
 9 {
10     int u,v,w;
11 }road[N<<1];
12 bool cmp(Edge a,Edge b)
13 {
14     return a.w<b.w;
15 }
16 
17 int find(int x)
18 {
19     return fa[x]==x?x:fa[x]=find(fa[x]);
20 }
21 
22 inline void read(int &x)
23 {
24     x=0; register char ch=getchar();
25     for(;ch>'9'||ch<'0';) ch=getchar();
26     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
27 }
28 
29 int AC()
30 {
31     freopen("ugrid.in","r",stdin);
32     freopen("ugrid.out","w",stdout);
33     read(n),read(m),read(k);
34     for(int i=1;i<=n;i++) fa[i]=i;
35     for(int i=1;i<=m;i++)
36     {
37         read(road[i].u),
38         read(road[i].v),
39         read(road[i].w);
40     }
41     long long ans=0; int cnt=0;
42     sort(road+1,road+m+1,cmp);
43     for(int fx,fy,i=1;i<=m;i++)
44     {
45         fx=find(road[i].u),fy=find(road[i].v);
46         if(fa[fy]==fx) continue;
47         fa[fy]=fx;
48         ans+=(long long)road[i].w;
49         if(++cnt==n-1) break;
50     }
51     cnt=0;k=find(k);
52     for(int i=1;i<=n;i++)
53         if(find(i)!=k) cnt++;
54     if(cnt) printf("%d
",cnt);
55     else  printf("%lld",ans);
56     return 0;
57 }
58 
59 int I_want_AC=AC();
60 int main(){;}

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。