澳门新葡亰8455下载app-网站注册正规靠谱 > 公司资讯 >
测试点分值

          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 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%的数据,电网无法覆盖全岛。

 

代码:

tarjan判断是否在同一个环里,爆栈、、、

图片 1图片 2

#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()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct Edde
{
    int x,y,z;
}edde[N];
struct Edge
{
    int to,from,next;
}edge[N<<1];
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();
    for(int i=1;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;
    }
    for(int i=1;i<=n;i++)
     if(!dfn[i]) tarjan(i);
    if(s>1) 
    {
        for(int i=1;i<=n;i++)
         if(belong[i]!=belong[k]) ans++;
        printf("%d",ans);    
        return 0;
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(edde+1,edde+1+m,cmp);
    for(int i=1;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;
        if(sum==n-1) break;
    } 
    printf("%lld",ans);
    return 0;
}

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()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct Edde
{
    int x,y,z;
}edde[N];
struct Edge
{
    int to,from,next;
}edge[N<<1];
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()
{
    for(int i=1;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();
    for(int i=1;i<=m;i++)
    {
       x=read(),y=read(),z=read();
       edde[i].x=x;
       edde[i].y=y;
       edde[i].z=z;
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(edde+1,edde+1+m,cmp);
    for(int i=1;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;
        if(sum==n-1) break;
    }
    pd();
    if(s) printf("%d",s);
    else printf("%lld",ans);
    return 0;
}

靠,什么鬼畜的输出

s输出用lld第一三个点wa,ans输出用I64d第4个点wa、、、、