1215. [Tyvj Aug11] 冗余电网
★ 输入文件：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个村庄，发电站要建在第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
具体含义见题目描述
接下来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%的数据，电网无法覆盖全岛。
代码：
tarjan判断是否在同一个环里，爆栈、、、
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 2100000
#define maxn 9999999
using namespace std;
bool vis[N];
long long ans;
int n,m,z,x,y,k,s,tot,sum,top,tim;
int fa[N],dfn[N],low[N],head[N],stack[N],belong[N];
int read()
{
,f=; char ch=getchar();
; ch=getchar();}
+ch-'; ch=getchar();}
return x*f;
}
struct Edde
{
int x,y,z;
}edde[N];
struct Edge
{
int to,from,next;
}edge[N<<];
int add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
}
int cmp(Edde a,Edde b)
{
return a.z<b.z;
}
int find(int x)
{
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
int tarjan(int now)
{
dfn[now]=low[now]=++tim;
stack[++top]=now,vis[now]=true;
for(int i=head[now];i;i=edge[i].next)
{
int t=edge[i].to;
if(vis[t]) low[now]=min(low[now],dfn[t]);
else if(!dfn[t]) tarjan(t),low[now]=min(low[now],low[t]);
}
if(low[now]==dfn[now])
{
s++;belong[now]=s;
for(;stack[top]!=now;top--)
{
int x=stack[top];
belong[x]=s,vis[x]=false;
}
top--,vis[now]=false;
}
}
int main()
{
freopen("ugrid4.in","r",stdin);
// freopen("ugrid.out","w",stdout);
n=read();m=read(),k=read();
;i<=m;i++)
{
x=read(),y=read(),z=read();
add(x,y),add(y,x);
edde[i].x=x;
edde[i].y=y;
edde[i].z=z;
}
;i<=n;i++)
if(!dfn[i]) tarjan(i);
)
{
;i<=n;i++)
if(belong[i]!=belong[k]) ans++;
printf("%d",ans);
;
}
;i<=n;i++) fa[i]=i;
sort(edde+,edde++m,cmp);
;i<=m;i++)
{
x=edde[i].x,y=edde[i].y;
int fx=find(x),fy=find(y);
if(fx==fy) continue;
fa[fx]=fy;sum++;
ans+=(long long)edde[i].z;
) break;
}
printf("%lld",ans);
;
}60分
并查集
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 210000
using namespace std;
bool vis[N];
long long ans;
int n,m,z,x,y,k,s,t,sum,fa[N];
int read()
{
,f=; char ch=getchar();
; ch=getchar();}
+ch-'; ch=getchar();}
return x*f;
}
struct Edde
{
int x,y,z;
}edde[N];
struct Edge
{
int to,from,next;
}edge[N<<];
int cmp(Edde a,Edde b)
{
return a.z<b.z;
}
int find(int x)
{
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
int pd()
{
;i<=n;i++)
if(find(i)!=find(k))
s++;
}
int main()
{
freopen("ugrid.in","r",stdin);
freopen("ugrid.out","w",stdout);
n=read();m=read(),k=read();
;i<=m;i++)
{
x=read(),y=read(),z=read();
edde[i].x=x;
edde[i].y=y;
edde[i].z=z;
}
;i<=n;i++) fa[i]=i;
sort(edde+,edde++m,cmp);
;i<=m;i++)
{
x=edde[i].x,y=edde[i].y;
int fx=find(x),fy=find(y);
if(fx==fy) continue;
fa[fx]=fy;sum++;
ans+=(long long)edde[i].z;
) break;
}
pd();
if(s) printf("%d",s);
else printf("%lld",ans);
;
}靠，什么鬼畜的输出
s输出用lld第一三个点wa，ans输出用I64d第4个点wa、、、、