218 条题解

  • 3
    @ 2020-07-20 11:21:46

    标准的最小生成树,因为N的规模,考虑路径压缩。然后你就能拿20分了
    然后把里面所有路程相关的变量改成double,你就可以拿90分了。
    最后,想一想,自己是不是没考虑过,把所有路线都连起来,还是不能够完成所有点的连接的情况?然后你就AC了......

  • 2
    @ 2020-10-09 09:10:33
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;
    
    namespace dts
    {
        struct edge
        {
            int x,y;
            double d;
        };
        
        int cmp_edge(edge a,edge b)
        {
            return a.d<b.d;
        }
        
        int n,m,cnt=0;
        int fa[100000];
        double s,ans=0;
        edge e[100000];
        
        int findfa(int p)
        {
            int ans=p;
            if (ans!=fa[ans])
                ans=findfa(fa[ans]);
            return ans;
        }
        
        void main()
        {
            scanf("%lf%d",&s,&n);
            for (m=0;~scanf("%d%d%lf",&e[m].x,&e[m].y,&e[m].d);m++)
                e[m].x--,e[m].y--;
            sort(&e[0],&e[m],cmp_edge);
            for (int i=0;i<n;i++)
                fa[i]=i;
            for (int i=0;i<m&&cnt<n-1;i++)
                if (findfa(e[i].x)!=findfa(e[i].y))
                {
                    fa[findfa(e[i].y)]=findfa(e[i].x);
                    cnt++;
                    ans+=e[i].d;
                }
            if (ans<=s&&cnt==n-1)
                printf("Need %.2lf miles of cable\n",ans);
            else
                printf("Impossible\n");
        }
    }
    
    int main(int argv,const char *argc[])
    {
        dts::main();
    }
    
  • 2
    @ 2019-02-23 13:30:59

    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int n,a,b;
    double c,s;
    struct cable
    {
    int x,y;
    double w;
    }e[100100];
    bool cmp(cable a,cable b)
    {
    return a.w<b.w;
    }
    int fa[100100];
    int find(int x)
    {
    if(fa[x]==x)
    return x;
    return fa[x]=find(fa[x]);
    }
    int m=0;
    int main()
    {
    scanf("%lf%d",&s,&n);
    for(int i=1;i<=n;i++)
    {
    fa[i]=i;
    }
    while(scanf("%d%d%lf",&a,&b,&c)!=EOF)
    {
    m++;
    e[m].x=a;
    e[m].y=b;
    e[m].w=c;
    }
    int cnt=0;
    double ans=0;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
    int fx,fy;
    fx=find(e[i].x);
    fy=find(e[i].y);
    if(fx!=fy)
    {
    fa[fy]=fx;
    cnt++;
    ans+=e[i].w;
    }
    if(cnt==n-1)
    break;
    }
    int k=find(1);
    for(int i=1;i<=n;i++)
    {
    if(find(i)!=k)
    {
    printf("Impossible\n");
    return 0;
    }
    }
    if(ans<=s)
    {
    printf("Need %.2lf miles of cable\n",ans);
    }
    else
    printf("Impossible\n");
    return 0;
    }

  • 2
    @ 2016-02-04 17:41:58

    身为提交n次才A的人,告诉那些最后一个点老WA的同志,
    Kerry可能根本不可能完成任务!!!!!!!!!

  • 1
    @ 2018-02-01 11:08:28
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    
    using namespace std;
    
    int p[100001];
    struct _Line {
        int u, v;
        double w;
    };
    
    int cmp(const _Line a, const _Line b) {
        return a.w < b.w;
    }
    
    int find(int x) {
        if (x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
    
    int main() {
        //freopen("a.txt","r",stdin);
        double s;
        int n;
        scanf("%lf%d", &s, &n);
        for (int i = 1; i <= n; i++) p[i] = i;
        _Line l[100001];
        int m = 0;
        while (scanf("%d%d%lf", &l[m].u, &l[m].v, &l[m].w) == 3) {
            m++;
        }
        sort(l, l + m, cmp);
        int flag = 0;
        double sum = 0;
        for (int i = 0; i < m; i++) {
            if (flag >= n - 1) break;
            int x = find(l[i].u);
            int y = find(l[i].v);
            if (x != y) {
                p[x] = y;
                sum += l[i].w;
            }
        }
        
        int t = find(1);
        for (int i = 1; i <= n; i++)
            if (find(i) != t) {
                printf("Impossible\n");
                return 0;
            }
        if (sum > s) {
            printf("Impossible");
        } else {
            printf("Need %.2lf miles of cable", sum);
        }
        //fclose(stdin);
        return 0;
    }
    

    这题没什么,第10个点需要判断所有点是否都在树里

  • 1
    @ 2017-05-07 22:19:30
    /*
    很明显是裸的Kruskal
    只是要判断一下最后答案是不是在s之内
    并且有没有把所有点连通起来
    因为我们用的是Kruskal算法
    所以判断是否把所有点连通我们只需要
    判断所有点是否在同一个集合中
    即根节点是否都相同即可
    注意精度问题
    蛮基础的问题的 也没啥陷阱
    练了练手
    Claris说得对
    都是套路啊
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=100004;
    struct node
    {
        int x,y;
        double w;
        bool operator < (const node&b)const
        {
            return w<b.w;
        }
    }a[MAXN];
    int fa[MAXN];
    int n;
    int m;
    double s;
    double ans;
    
    int getfather(int x)
    {
        return fa[x]==x?x:fa[x]=getfather(fa[x]);
    }
    
    void inline Add_Edge(int x,int y,double w)
    {
        m++;
        a[m].x=x;   a[m].y=y;   a[m].w=w;
    }
    
    void init()
    {
        int x,y;
        double w;
        cin>>s>>n;
        while(scanf("%d%d%lf",&x,&y,&w)==3)
            Add_Edge(x,y,w);
        for(int i=1;i<=n;i++)
            fa[i]=i;
    }
    
    void Kruskal()
    {
        int tot=0;
        sort(a+1,a+m+1);
        for(int i=1;i<=m;i++)
        {
            int fx=getfather(a[i].x);
            int fy=getfather(a[i].y);
            if(fx!=fy)
            {
                tot++;
                fa[fx]=fy;
                ans+=a[i].w;
                if(tot==n-1)
                    break;
            }
        }
    }
    
    void out()
    {
        int k=getfather(1);
        for(int i=2;i<=n;i++)
            if(getfather(i)!=k)
            {
                cout<<"Impossible"<<endl;
                return;
            }
        if(ans<=s)
            printf("Need %.2lf miles of cable\n",ans);
        else
            cout<<"Impossible"<<endl;
    }
    
    int main()
    {
        init();
        Kruskal();
        out();
        return 0;
    }
         
    
  • 0
    @ 2017-02-14 11:47:33

    编译成功

    测试数据 #0: Accepted, time = 265 ms, mem = 2692 KiB, score = 10
    测试数据 #1: Accepted, time = 125 ms, mem = 2688 KiB, score = 10
    测试数据 #2: Accepted, time = 765 ms, mem = 2688 KiB, score = 10
    测试数据 #3: Accepted, time = 500 ms, mem = 2688 KiB, score = 10
    测试数据 #4: Accepted, time = 734 ms, mem = 2688 KiB, score = 10
    测试数据 #5: Accepted, time = 859 ms, mem = 2688 KiB, score = 10
    测试数据 #6: Accepted, time = 625 ms, mem = 2692 KiB, score = 10
    测试数据 #7: Accepted, time = 656 ms, mem = 2688 KiB, score = 10
    测试数据 #8: Accepted, time = 640 ms, mem = 2688 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 2692 KiB, score = 10
    Accepted, time = 5169 ms, mem = 2692 KiB, score = 100

    可能是评测机有问题或者现在的数据改了。。我说怎么和其他dalao的时间差那么大。。

    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<vector>
    #include<sstream>
    #include<algorithm>
    #include<string>
    #include<cstdio>
    #include<math.h>
    #include<map>
    #include<cctype>
    #include<queue>
    #include<functional>
    #include<set>
    #define lson l , m , rt << 1  
    #define rson m + 1 , r , rt << 1 | 1  
    #define Mem(a,b) memset((a),(b),sizeof((a)))
    #define Sy system("pause")
    const int maxn = 100000 + 10;
    const int INF = 1e9;
    using namespace std;
    typedef long long LL;
    struct Edge
    {
        int u, v; double w;
        Edge(){}
        Edge(int a, int b, double c) :u(a), v(b), w(c){}
    
    };
    inline bool cmp(Edge& a, Edge& b){
        return a.w < b.w;
    }
    //vector<Edge> edges;
    Edge edges[maxn];
    int p[maxn];
    double s;
    int n, m = 0;
    int find(int x){
        return p[x] == x ? x : (p[x] = find(p[x]));
    }
    void addedge(int a, int b, double c){
        edges[m++] = Edge(a, b, c);
    }
    int main(){
        scanf("%lf%d", &s, &n);
        int x, y; double z;
        for (int i = 1; i <= n; i += 1)
            p[i] = i;
        while (scanf("%d %d %lf", &x, &y, &z) == 3){
            addedge(x, y, z);
        }
        sort(edges, edges + m, cmp);
        double ans = 0.0;
        int count = n;
        for (int i = 0; i < m; i += 1){
            x = edges[i].u, y = edges[i].v; z = edges[i].w;
            int a = find(x), b = find(y);
            if (a != b){
                p[a] = b; ans += z;
                count -= 1;
                if (count == 1)
                    break;
            }
        }
        int p1 = find(1);
        for (int i = 2; i <= n; i += 1)
            if (p1 != find(i)){
                printf("Impossible\n");
                return 0;
            }
        if (ans <= s)
            printf("Need %.2f miles of cable\n", ans);
        else
            printf("Impossible\n");
        return 0;
    }
    
  • 0
    @ 2016-10-07 10:26:03
    彻底被输入坑了,里面的m是边数,当时身体不清楚
    //这个题目有个坑,开始输入的是n,但实际上的边数为m,改了4次都没有过,一看题解才知道 
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    double s,ans=0;
    int n,num=0,m=0,k;
    int f[100001];
    
    struct ljh
    {
        int x,y;
        double z;
    }a[100001];
    
    int cmp(ljh a,ljh b)
    {
        return a.z<b.z;
    }
    
    int find(int x)
    {
        if(f[x]!=x)return f[x]=find(f[x]);
        return x;
    }
    
    int main()
    {
        scanf("%lf%d",&s,&n);
    //  cout<<s<<endl;
        for(int i=1;i<=n;i++)f[i]=i;
    //  for(int i=1;i<=n;i++)scanf("%d%d%lf",&a[i].x,&a[i].y,&a[i].z);用的这种方法输入,被坑了 
        while(cin>>k)
        {
            m++;
            a[m].x=k;
            cin>>a[m].y>>a[m].z;
        }
    //    while(scanf("%d%d%lf",&a[m].x,&a[m].y,&a[m].z)==3)m++;
        sort(a+1,a+m+1,cmp);
    //  for(int i=1;i<=n;i++)
    //  {
    //      cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<endl;
    //  }
        for(int i=1;i<=m;i++)
        {
            int u=find(a[i].x);
            int v=find(a[i].y);
            if(u!=v)
            {
                ans+=a[i].z;
                f[v]=u;
                num++;
            }
            if(num==n-1)break;
        }
        int r=find(1);//不加上这个判断会挂掉最后一个点 
        for(int i=1;i<=n;i++)
        if(find(i)!=r||ans>s)
        {
          cout<<"Impossible";
          return 0;
        }
        printf("Need %.2f miles of cable",ans);
    //  cout<<ans;
        return 0;
    }
    
  • 0
    @ 2015-11-19 21:57:46

    重要提示:输出时不能用%.2lf,要用%.2f,否则会WA8个点
    裸的Kruskal
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #define rep(i,l,r) for(int i=l; i<=r; i++)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define travel(x) for(int i=last[x]; i; i=edge[i].pre)
    using namespace std;
    typedef long long ll;
    const int INF = 0x3f3f3f3f;
    const int maxn = 100010;
    struct Edge{
    int from,to;
    double cost;
    }edge[maxn];
    int n,m=0,x,y,u,v,a,b,tot=0,cnt=0,father[maxn];
    double s,z,total=0;
    inline bool cmp(const Edge &x, const Edge &y){
    return x.cost < y.cost;
    }
    inline void addedge(int x,int y,double z){
    edge[++tot].from = x;
    edge[tot].to = y;
    edge[tot].cost = z;
    }
    int getfather(int x){
    return father[x] == x ? x : father[x] = getfather(father[x]);
    }
    void kruskal(){
    rep(i,1,n) father[i] = i;
    rep(i,1,m){
    u = edge[i].from; v = edge[i].to;
    a = getfather(u); b = getfather(v);
    if (a != b){
    cnt++;
    father[a] = b;
    total += edge[i].cost;
    if (cnt == n-1) break;
    }
    }
    }
    int main(){
    scanf("%lf%d",&s,&n);
    while (scanf("%d%d%lf",&x,&y,&z) == 3){
    m++;
    addedge(x,y,z);
    }
    sort(edge+1,edge+m+1,cmp);
    kruskal();
    int fa1 = getfather(1);
    rep(i,2,n) if (getfather(i) != fa1){
    printf("Impossible\n");
    return 0;
    }
    if (total <= s) printf("Need %.2f miles of cable\n",total);
    else printf("Impossible\n");
    return 0;
    }

  • 0
    @ 2015-11-09 09:35:04

    记录信息
    评测状态 Accepted
    题目 P1045 Kerry 的电缆网络
    递交时间 2015-11-09 09:34:05
    代码语言 C++
    评测机 VijosEx
    消耗时间 1697 ms
    消耗内存 3800 KiB
    评测时间 2015-11-09 09:34:10
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 109 ms, mem = 3800 KiB, score = 10
    测试数据 #1: Accepted, time = 62 ms, mem = 3792 KiB, score = 10
    测试数据 #2: Accepted, time = 234 ms, mem = 3800 KiB, score = 10
    测试数据 #3: Accepted, time = 156 ms, mem = 3800 KiB, score = 10
    测试数据 #4: Accepted, time = 249 ms, mem = 3796 KiB, score = 10
    测试数据 #5: Accepted, time = 218 ms, mem = 3796 KiB, score = 10
    测试数据 #6: Accepted, time = 249 ms, mem = 3800 KiB, score = 10
    测试数据 #7: Accepted, time = 202 ms, mem = 3796 KiB, score = 10
    测试数据 #8: Accepted, time = 218 ms, mem = 3796 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 3792 KiB, score = 10
    Accepted, time = 1697 ms, mem = 3800 KiB, score = 100
    代码
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    struct point{
    int u,v;
    double val;
    }edge[100010];
    int fa[100010];
    double val[200010];
    int find(int x){
    return (fa[x]==x)?x:fa[x]=find(fa[x]);
    }
    bool cmp(point a,point b)
    {
    return a.val<b.val;
    }
    using namespace std;
    int main()
    {
    int n;double L;
    scanf("%lf%d",&L,&n);
    int m=1;
    while(scanf("%d%d%lf",&edge[m].u,&edge[m].v,&edge[m].val)==3)++m;
    m--;
    for(int i=1;i<=n;i++)fa[i]=i;
    sort(edge+1,edge+m+1,cmp);
    double ans=0.0;
    for(int i=1;i<=m;i++)
    {
    int x=edge[i].u;
    int y=edge[i].v;
    x=find(x);
    y=find(y);
    if(x!=y)
    {
    fa[x]=y;
    ans+=edge[i].val;
    }
    }
    int flag=1;
    int x=find(1);
    for(int i=2;i<=n&&flag;i++)if(x!=find(i))flag=0;
    if(ans>L||!flag)
    printf("Impossible\n");
    else
    printf("Need %.2f miles of cable\n",ans);

    return 0;
    }

  • 0
    @ 2015-10-10 14:44:06

    [codep]
    program p1045;
    type rec=record
    x,y:longint;
    len:extended;
    end;
    var s,ans:extended;
    a:array[0..100000]of rec;
    u:array[0..100000]of boolean;
    i,k,m,n,bx,by:longint;
    b:array[0..100000] of longint;
    f:boolean;
    procedure qsort(s,t:longint);
    var i,j:longint;x:rec;
    begin
    i:=s;
    j:=t;
    x:=a[s];
    while i<j do
    begin
    while(a[j].len>x.len)and(i<j) do
    j:=j-1;
    if j>i then
    begin
    a[i]:=a[j];
    i:=i+1;
    end;
    while(a[i].len<x.len)and(i<j) do
    i:=i+1;
    if i<j then
    begin
    a[j]:=a[i];
    j:=j-1;
    end;
    a[i]:=x;
    end;
    if s<(i-1) then qsort(s,i-1);
    if (i+1)<t then qsort(i+1,t);
    end;
    function getb(x:longint):longint;
    var y:longint;
    begin
    while b[x]<>x do
    begin
    y:=b[x];
    b[x]:=b[y];
    x:=y;
    end;
    exit(x);
    end;
    procedure find_bian;
    begin
    k:=0;
    ans:=0;
    fillchar(u,sizeof(u),true);
    for i:=1 to m do
    begin
    bx:=getb(a[i].x);
    by:=getb(a[i].y);
    if bx=by then continue;
    b[a[i].y]:=bx;
    b[by]:=bx;
    u[a[i].x]:=false;
    u[a[i].y]:=false;
    ans:=ans+a[i].len;
    end;
    end;
    begin
    randomize;
    readln(s);
    readln(n);
    m:=0;
    while not eof do
    begin
    inc(m);
    readln(a[m].x,a[m].y,a[m].len);
    end;
    qsort(1,m);
    for i:=1 to n do b[i]:=i;
    find_bian;
    f:=true;
    for i:=1 to n do
    if u[i] then
    begin
    f:=false;
    break;
    end;
    if (ans<=s)and f then writeln('Need ',ans:0:2,' miles of cable')
    else writeln('Impossible');
    end.
    [/codep]

  • 0
    @ 2015-09-08 18:43:01

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxx=10000000;

    double l;
    int n;
    struct tree
    {
    int x;
    int y;
    double len;
    }map[100000+5];

    double way[100000+5];
    int root[100000+5];

    int com(const tree &a,const tree &b)
    {
    return (a.len<b.len);
    }

    int find(int t)
    {
    if(root[t]==t)
    return t;
    root[t]=find(root[t]);
    return root[t];

    }

    void unite(int a,int b)
    {
    a=find(a);
    b=find(b);
    root[a]=b;

    }

    int main()
    {
    //freopen("use.in","r",stdin);
    //freopen("use.out","w",stdout);

    cin>>l>>n;

    for(int i=1;i<=n;i++)
    root[i]=i;

    int temp;
    int m=0;
    while(cin>>temp)
    {
    m++;
    map[m].x=temp;
    cin>>map[m].y>>map[m].len;
    }

    sort(map+1,map+m+1,com);

    int k=0;
    double sum=0;
    for(int i=1;i<=m;i++)
    {
    if(find(map[i].x)!=find(map[i].y))
    {
    unite(map[i].x,map[i].y);
    sum+=map[i].len;
    k++;
    }

    if(k==n-1)
    break;
    }
    /*
    for(int i=1;i<=n;i++)
    root[i]=find(i);
    //*/

    int r=find(1);
    for(int i=1;i<=n;i++)
    if(find(i)!=r||sum>l)
    {
    cout<<"Impossible";
    return 0;
    }

    /*for(int i=1;i<=m;i++)
    cout<<map[i].x<<" "<<map[i].y<<" "<<map[i].len<<endl;*/
    printf("Need %.2f miles of cable",sum);

    return 0;

    }

  • 0
    @ 2015-08-19 16:27:42

    纯粹的最小生成树问题,采用kruscal算法生成最小生成树之后比较所需最小代价与所给长度比较即可。

    ###代码如下

    program p1045;
    type rec=record
    s,e:longint;
    v:real;
    end;
    var n,m,sum:longint;
    len,cost:real;
    map:array[1..100000] of rec;
    i,j,k:longint;
    father:array[1..100000] of longint;
    rank:array[1..100000] of longint;
    procedure qsort(i,j:longint);
    var l,r:longint;
    mid:real;
    temp:rec;
    begin
    l:=i;
    r:=j;
    mid:=map[(l+r)>>1].v;
    while l<=r do
    begin
    while map[l].v<mid do inc(l);
    while map[r].v>mid do dec(r);
    if l<=r then
    begin
    temp:=map[l];
    map[l]:=map[r];
    map[r]:=temp;
    inc(l);
    dec(r);
    end;
    end;
    if l<j then qsort(l,j);
    if i<r then qsort(i,r);
    end;

    function find(x:longint):longint;
    begin
    if father[x]=x
    then exit(x);
    father[x]:=find(father[x]);
    exit(father[x]);
    end;

    procedure unite(a,b:longint);
    var fa,fb:longint;
    begin
    fa:=find(father[a]);
    fb:=find(father[b]);
    if rank[fa]>rank[fb]
    then
    father[fb]:=fa
    else
    father[fa]:=fb;
    end;

    begin
    readln(len);
    readln(n);
    m:=0;
    while not eof do
    begin
    inc(m);
    with map[m] do
    readln(s,e,v);
    end;
    qsort(1,m);
    for i:=1 to m do
    begin
    father[i]:=i;
    rank[i]:=1;
    end;
    for i:=1 to m do
    begin
    if find(map[i].s)<>find(map[i].e)
    then
    begin
    unite(map[i].s,map[i].e);
    inc(sum);
    cost:=cost+map[i].v;
    end;
    end;
    if (cost>len) or (sum<>(n-1))
    then write('Impossible')
    else write('Need ',cost:0:2,' miles of cable');
    end.

    ###评测结果

    测试数据 #0: Accepted, time = 31 ms, mem = 3132 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 3132 KiB, score = 10
    测试数据 #2: Accepted, time = 62 ms, mem = 3132 KiB, score = 10
    测试数据 #3: Accepted, time = 46 ms, mem = 3136 KiB, score = 10
    测试数据 #4: Accepted, time = 62 ms, mem = 3132 KiB, score = 10
    测试数据 #5: Accepted, time = 62 ms, mem = 3128 KiB, score = 10
    测试数据 #6: Accepted, time = 78 ms, mem = 3132 KiB, score = 10
    测试数据 #7: Accepted, time = 62 ms, mem = 3132 KiB, score = 10
    测试数据 #8: Accepted, time = 62 ms, mem = 3132 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 3128 KiB, score = 10
    Accepted, time = 480 ms, mem = 3136 KiB, score = 100

  • 0
    @ 2014-12-23 18:01:57

    无语
    输入的时候。
    read(s,n);
    全wa
    改成
    readln(s);
    readln(n);
    AC
    揪心

    var a,x,y:array[0..100000] of longint;
    p:array[0..100000] of boolean;
    b:array[0..100000] of real;
    s,ans:real;
    n,m,i,j,k,l:longint;

    procedure sort(l,r: longint);
    var
    i,j: longint;
    xx:real;
    begin
    i:=l;
    j:=r;
    xx:=b[(l+r) div 2];
    repeat
    while b[i]<xx do
    inc(i);
    while xx<b[j] do
    dec(j);
    if not(i>j) then
    begin
    b[0]:=b[i]; b[i]:=b[j]; b[j]:=b[0];
    x[0]:=x[i]; x[i]:=x[j]; x[j]:=x[0];
    y[0]:=y[i]; y[i]:=y[j]; y[j]:=y[0];
    inc(i);
    j:=j-1;
    end;
    until i>j;
    if l<j then
    sort(l,j);
    if i<r then
    sort(i,r);
    end;

    function fa(i:longint):longint;

    begin
    if a[i]=i then fa:=i
    else
    begin
    a[i]:=fa(a[i]);
    fa:=a[i];
    end;
    end;

    procedure kru;

    var r,fx,fy:longint;

    begin
    fillchar(p,sizeof(p),false);
    ans:=0;
    for r:=1 to m do
    begin
    fx:=fa(x[r]);
    fy:=fa(y[r]);
    if fx<>fy then
    begin
    p[x[r]]:=true;
    p[y[r]]:=true;
    a[y[r]]:=fx;
    a[fy]:=fx;
    ans:=ans+b[r];
    end;
    end;

    end;

    begin
    readln(s);
    readln(n);
    m:=0;
    while not eof do
    begin
    inc(m);
    readln(x[m],y[m],b[m]);
    end;
    sort(1,m);

    for l:=1 to n do
    a[l]:=l;
    kru;
    p[0]:=true;
    for l:=1 to n do
    if not(p[l]) then begin p[0]:=false; break; end;
    if (ans<=s) and (p[0]) then writeln('Need ',ans:0:2,' miles of cable') else write('Impossible');
    end.

  • 0
    @ 2014-10-03 00:21:52

    妈蛋。。合并的时候写成 find(x)=fa[find(y)] 脑洞是大啊QAQ
    挺水的。。WA了好几次

  • 0
    @ 2012-11-17 19:21:55

    唉,交了5次才AC.

    就是Kruscal+并查集.

    最后的问题是吧M全打成了N.这样就按点数来排序,每次只判断点数次的边.

    只有50分..给一次AC的神牛跪烂了.....

  • 0
    @ 2012-11-08 18:47:42

    WA了若干次==

    1. 注意图是否连通

    2. 用double,不要用float

  • 0
    @ 2012-08-10 20:27:49

    kruscal算法,

    这道题是最基础最典型的最小生成树题目(在n个点之间连n-1条边使得代价最小)

    先将数据按电缆长度从小到大排序,

    当前做到点 x[i] y[i] ,然后用并查集查询x[i]与y[i]是否拥有同一祖先,

    如果不拥有同一祖先,就将y[i]这个点加入x[i]所在的树中,然后将两者合并在一起,然后用一数组来判重

    直到做完为止...

    贴一下俺的代码

    var

    s,ans:extended;

    x,y:array[0..100000] of longint;

    len:array[0..100000] of extended;

    u:array[0..100000] of boolean;

    i,j,k,l,m,n,fx,fy:longint;

    father:array[0..100000] of longint;

    f:boolean;

    procedure qsort(l,r:longint);

    var

    i,j:longint;

    m:extended;

    begin

    i:=l;

    j:=r;

    m:=len[random(j-i+1)+i];

    repeat

    while len[i]m do dec(j);

    if ij;

    if i

  • 0
    @ 2012-07-29 11:32:51

    kruscal

    编译通过... 

    ├ 测试数据 01:答案正确... 0ms 

    ├ 测试数据 02:答案正确... 0ms 

    ├ 测试数据 03:答案正确... 0ms 

    ├ 测试数据 04:答案正确... 0ms 

    ├ 测试数据 05:答案正确... 0ms 

    ├ 测试数据 06:答案正确... 0ms 

    ├ 测试数据 07:答案正确... 9ms 

    ├ 测试数据 08:答案正确... 0ms 

    ├ 测试数据 09:答案正确... 0ms 

    ├ 测试数据 10:答案正确... 0ms 

    ---|---|---|---|---|---|---|---|- 

    Accepted 有效得分:100 有效耗时:9ms 

  • 0
    @ 2010-07-17 23:06:20

    第一次只有第十个点没过

    第二次只过了第十个点

    第三次AC。。。。。。

信息

ID
1045
难度
7
分类
树结构 点击显示
标签
(无)
递交数
4912
已通过
986
通过率
20%
被复制
5
上传者