题解

127 条题解

  • 3
    @ 2019-04-29 19:35:17

    并查集+prim(贪心)
    得到K块连通分量要选择N-K条边,直接选最小的N-K条,要注意选的每条边两个端点不能已连通。
    判断是否已连通可以用并查集实现。

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef struct
    {
        int a,b;
        int w;
    }edge;
    
    int n,m,k;
    edge e[10000];
    int f[1001];
    
    int fi(int x)
    {
        if(f[x]==x)
        {
            return x;
        }
        return f[x]=fi(f[x]);
    }
    
    void un(int a,int b)
    {
        int x=fi(a);
        int y=fi(b);
        if(x!=y)
        {
            f[y]=x;
        }
    }
    
    bool comp(edge a,edge b)
    {
        return a.w<b.w;
    }
    
    int main()
    {
        cin>>n>>m>>k;
        if(m<n-k)
        {
            cout<<"No Answer"<<endl;
            return 0;
        }
        int i;
        for(i=0;i<=n;i++)
        {
            f[i]=i;
        }
        for(i=0;i<m;i++)
        {
            cin>>e[i].a>>e[i].b>>e[i].w;
        }
        sort(e,e+m,comp);
        int ans=0;
        int acc=n-k;
        for(i=0;i<m;i++)
        {
            if(fi(e[i].a)!=fi(e[i].b))
            {
                acc--;
                ans+=e[i].w;
                un(e[i].a,e[i].b);
                if(acc==0)
                {
                    break;
                }
            }
        }
        if(acc==0)
        {
            cout<<ans<<endl;
        }
        else
        {
            cout<<"No Answer"<<endl;
        }
        return 0;
    }
    
  • 2
    @ 2017-07-13 19:26:04

    prim算法
    求出n个云朵的最小生成树的代价,将它们连成一个棉花糖,然后选取最小生成树中代价最大的k-1个代价,将最小生成树的代价减去这k-1个代价即为花费最少。

    轻松水过。。
    var
    n,m,i,j,k:longint;
    selected:array[0..10000] of longint;
    e:array[0..10000,1..2] of longint;
    value:array[0..10000] of longint;
    t:array[0..10000] of longint;
    a:array[0..10000] of longint;
    min,mine,valuet,g:longint;
    procedure sort(l,r: longint);
    var
    i,j,x,y: longint;
    begin
    i:=l;
    j:=r;
    x:=a[(l+r) div 2];
    repeat
    while a[i]>x do
    inc(i);
    while x>a[j] do
    dec(j);
    if not(i>j) then
    begin
    y:=a[i];
    a[i]:=a[j];
    a[j]:=y;
    inc(i);
    j:=j-1;
    end;
    until i>j;
    if l<j then
    sort(l,j);
    if i<r then
    sort(i,r);
    end;

    begin
    read(n,m,k);
    for i:=1 to m do
    readln(e[i,1],e[i,2],value[i]);
    fillchar(selected,sizeof(selected),0);
    fillchar(t,sizeof(t),0);
    valuet:=0;
    for i:=1 to n-1 do
    begin
    min:=maxlongint;
    mine:=0;
    for j:=1 to m do
    if selected[j]=0 then
    if ((t[e[j,1]]=0) xor (t[e[j,2]]=0)) or (i=1) then
    if value[j]<min then
    begin min:=value[j];mine:=j;end;
    inc(g);
    a[g]:=min;
    selected[mine]:=1;
    t[e[mine,1]]:=1;
    t[e[mine,2]]:=1;
    valuet:=valuet+min;
    end;
    sort(1,g);
    for i:=1 to k-1 do
    valuet:=valuet-a[i];
    writeln(valuet);
    end.

  • 1
    @ 2019-02-07 23:30:56

    #1 Accepted 2ms 700.0 KiB
    #2 Accepted 2ms 616.0 KiB
    #3 Accepted 1ms 232.0 KiB
    #4 Accepted 5ms 356.0 KiB
    #5 Accepted 4ms 372.0 KiB
    #6 Accepted 5ms 348.0 KiB
    #7 Accepted 4ms 348.0 KiB
    #8 Accepted 4ms 348.0 KiB
    #9 Accepted 4ms 360.0 KiB
    #10 Accepted 4ms 352.0 KiB
    //kruskal算法
    #include <bits/stdc++.h>
    using namespace std;
    int f[1005],res,ans=0,n,m,k,x,y,l;
    struct edge
    {
    int u,v,w;
    }a[10005];
    bool cmp(edge a,edge b)
    {
    return a.w<b.w;
    }
    int find(int x)
    {
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);

    }
    void kruskal()
    {
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++)
    {
    int u=find(a[i].u),v=find(a[i].v);
    if(u!=v)
    {
    ans+=a[i].w; f[u]=v; res--;
    }
    if(res==k) return ;
    }
    }
    int main()
    {
    scanf("%d%d%d",&n,&m,&k);
    res=n;
    for(int i=1;i<=m;i++)
    {
    scanf("%d%d%d",&x,&y,&l);
    a[i].u=x; a[i].v=y; a[i].w=l;
    }
    sort(a+1,a+m+1,cmp);
    kruskal();
    if(res!=k) printf("No Answer");
    else printf("%d",ans);
    return 0;
    }

  • 1
    @ 2017-09-22 17:08:26

    MST后统计联通块个数然后从大到小删边

    #include<bits/stdc++.h>
    using namespace std;
    const int N=10000+10,M=100000+10;
    typedef long long ll;
    int n,m,K,len,last[N],fa[N];
    bool vis[N];
    struct Edge
    {
        int from,to,val;
        bool operator <(const Edge &rhs)const {
            return rhs.val>val;
        }
    }e[M];
    int find(int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}
    void Kruskal()
    {
        ll tot=0,ans=0,cnt=0;
        for(int i=1;i<=n;i++)fa[i]=i;
        for(int i=1;i<=m;i++)
        {
            int idx=find(e[i].from),idy=find(e[i].to);
            if(idx==idy)continue;
            ans+=e[i].val;
            fa[idx]=idy;
            vis[i]=1;
            cnt++;
        }
        int k=n-cnt;
        for(int i=m;i>=1&&k<K;i--)if(vis[i])tot+=e[i].val,k++;
        if(k<K)printf("No Answer\n"); 
        else printf("%lld\n",ans-tot);
    }
    int main()
    {
        scanf("%d%d%d",&n,&m,&K);
        for(int u,v,w,i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            e[i].from=u;e[i].to=v;e[i].val=w;
        }
        sort(e+1,e+1+m);
        Kruskal();
        return 0;
    }
    
  • 1
    @ 2017-06-07 14:49:34
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    struct edge_1
    {
        int x,y,d;
    };
    
    int n,m,t,cnt,ans;
    vector<int> fa;
    vector<edge_1> e;
    
    void c_v_1()
    {
        fa.resize(0);
        e.resize(0);
    }
    
    bool cmp_edge_1(edge_1 x,edge_1 y)
    {
        return x.d<y.d;
    }
    
    int find_fa_1(int x)
    {
        return ((fa[x]==x)?x:(fa[x]=find_fa_1(fa[x])));
    }
    
    int unite_1(int x,int y)
    {
        if (fa[(fa[y]=find_fa_1(fa[y]))]!=(fa[x]=find_fa_1(fa[x])))
        {
            fa[fa[y]]=fa[x];
            return 1;
        }
        else
            return 0;
    }
    
    int main()
    {
        while (~scanf("%d%d%d",&n,&m,&t))
        {
            c_v_1();
            fa.resize(n+1,0);
            for (int i=1;i<=n;i++)
                fa[i]=i;
            e.resize(m+1);
            for (int i=1;i<=m;i++)
                scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].d);
            sort(e.begin()+1,e.end(),cmp_edge_1);
            cnt=ans=0;
            for (int i=1;i<=m&&cnt<n-t;i++)
            {
                int suc=unite_1(e[i].x,e[i].y);
                cnt+=suc;
                ans+=e[i].d*suc;
            }
            if (cnt>=n-t)
                printf("%d\n",ans);
            else
                printf("No Answer\n");
        }
    }
    
  • 1
    @ 2015-08-19 16:24:09

    因为共有n朵云并且一朵云就可以构成一个棉花糖,所以不用云构造花费为0,那么就要留出k-1朵云单独作为一个棉花糖,即将剩下的n-(k-1)朵云构造成一棵最小生成树,即当加入的边数=n-(k-1)-1时构造完成。此时构造的为最小生成树,构造这个棵树花费最小,其他花费为0,所以这样就以最小的花费构造出了k个棉花糖;
    算法以并查集优化的kruscal来构造即可。

    ###代码如下

    program p1234;
    type rec=record
    s,e,v:longint;
    end;
    var i,j,n,m,k,cost:longint;
    father:array[1..1000] of longint;
    map:array[1..10000] of rec;
    procedure qsort(i,j:longint);
    var l,r,mid:longint;
    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);
    begin
    father[find(father[a])]:=find(father[b]);
    end;

    begin
    readln(n,m,k);
    if n<k then
    begin
    write('No Answer');
    exit;
    end;
    for i:=1 to m do
    readln(map[i].s,map[i].e,map[i].v);
    for i:=1 to n do
    father[i]:=i;
    qsort(1,m);
    for i:=1 to m do
    begin
    if j=n-(k-1)-1
    then
    begin
    break;
    end;
    if find(map[i].s)<>find(map[i].e)
    then
    begin
    unite(map[i].s,map[i].e);
    inc(j);
    cost:=cost+map[i].v;
    end;
    end;
    write(cost);
    end.
    ###评测结果

    测试数据 #0: Accepted, time = 0 ms, mem = 904 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 904 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 904 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 900 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 904 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 904 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    Accepted, time = 15 ms, mem = 904 KiB, score = 100

  • 0
    @ 2021-04-10 14:37:03

    kruskal

    #include <cstdio>
    #include <algorithm>
    int n, m, kk;
    struct edge {
        int u, v, q;
    }a[500001];
    int pr[5001], k[5001];
    /*
    inline int RD() {
        int x = 0, f = 1;
        char c = getchar();
        while(c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}
        while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    }
    */
    bool cmp(edge x, edge y) {
        return x.q < y.q;
    }
    int fr(int x) {
        int xr = x;
        while (pr[xr] != x) {
            x = pr[x];
    //      printf ("%d %d\n", xr, x);
            xr = pr[xr];
            pr[x] = pr[xr];
        }
        return xr;
    }
    bool nv(int x, int y) {
        int xr, yr;
        xr = fr(x);
        yr = fr(y);
        if (xr == yr) return false;
        if (k[xr] > k[yr]) pr[yr] = xr;
        else if (k[yr] > k[xr]) pr[xr] = yr;
        else {
            pr[yr] = xr;
            ++k[xr];
        }
        return true;
    }
    int main() {
        int s = 0, tt = 0;
        scanf ("%d%d%d", &n, &m, &kk);
        for (int i = 1; i <= n; ++i) pr[i] = i;
        for (int i = 1; i <= m; ++i) {
            scanf ("%d%d%d", &a[i].u, &a[i].v, &a[i].q);
        }
        std::sort(a + 1, a + m + 1, cmp);
        for (int i = 1; i <= m; ++i) {
            if (nv(a[i].u, a[i].v)) {s += a[i].q; ++tt;}
            if (tt == n - kk) {printf ("%d\n", s); return 0;}
        }
        if (tt == n - kk) {printf ("%d\n", s); return 0;}
        else puts("No Answer\n");
    }
    
  • 0
    @ 2017-08-14 09:48:28

    //Kruskal轻松水过
    #include<iostream>
    #include<algorithm>
    #include<stdlib.h>
    using namespace std;
    int d,fa[1001],ra[1001];
    struct Edge
    {
    int a;
    int b;
    int v;
    }edge[10001];
    int ff(int a)
    {
    if (fa[a]==a)
    return a;
    else return ff(fa[a]);
    }
    bool hb(int a,int b)
    {
    int r1,r2;
    r1=ff(a);
    r2=ff(b);
    if (r1==r2)
    return false;
    else
    {
    if (ra[r1]<ra[r2])
    {
    fa[r1]=r2;
    ra[r2]+=ra[r1];
    }
    else
    {
    fa[r2]=r1;
    ra[r1]+=ra[r2];
    }
    return true;
    }
    }
    bool cmp(Edge a, Edge b)
    {
    return a.v<b.v;
    }
    int main()
    {
    int a,b,c,n,m,k,sum=0;
    cin>>n>>m>>k;
    d=n;
    for(int i=1;i<=n;i++)
    {
    fa[i]=i;
    ra[i]=1;
    }
    for (int i=1;i<=m;i++)
    {
    cin>>edge[i].a>>edge[i].b>>edge[i].v;

    }
    sort(edge+1,edge+1+m,cmp);
    for (int i=1;i<=m;i++)
    {
    if (hb(edge[i].a,edge[i].b))
    {
    d--;
    sum+=edge[i].v;
    if (d==k)
    {
    cout<<sum;
    return 0;
    }
    }
    }
    cout<<"No Answer";
    return 0;

    }

  • 0
    @ 2017-01-17 19:59:31
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    struct node
    {
        int prev,next,weight;
        bool operator<(const node &t) const
        {
            if (weight!=t.weight) return weight<=t.weight;
                else return next>=t.next;
        }
    }cloud[10050];
    
    int num,n,m,Father[10050],Rank[10050],max_connect=0,ans,k;
    
    void Init()
    {
        for (int i=0;i<10050;i++)
        {
            Father[i]=i;
            Rank[i]=1;
        }
    }
    
    int Get_Father(int x)
    {
        if (x==Father[x])
        {
            return x;
        }
        else
        {
            return Father[x]=Get_Father(Father[x]);
        }
    }
    
    void Merge(int a,int b)
    {
        int xa=Get_Father(a),xb=Get_Father(b);
        if (xa!=xb)
        {
            Father[xb]=xa;
            Rank[xa]+=Rank[xb];
            max_connect++;
        }
    }
    
    bool Find(int a,int b)
    {
        return (Get_Father(a)==Get_Father(b));
    }
    
    int main()
    {
        cin >> n >> m >> k;
        max_connect=0;
        ans=0;
        Init();
        for (int i=1;i<=m;i++)
        {
            cin >> cloud[i].prev >> cloud[i].next >> cloud[i].weight; 
        }
        sort(cloud+1,cloud+m+1);
        for (num=1;num<=m;num++)
        {
            //cout << "***" << cloud[num].prev << " " << cloud[num].next << endl;
            if (!Find(cloud[num].prev,cloud[num].next))
            {
                Merge(cloud[num].prev,cloud[num].next);
                ans+=cloud[num].weight;
                //cout << cloud[num].weight << " " << max_connect << endl;
            }
            if (max_connect==n-k)
                break; 
        }
        if (max_connect!=n-k) cout << "No Answer" << endl;
            else cout << ans << endl;
        return 0;
    }
    

    裸kruskal,除了n-k要注意注意

  • 0
    @ 2016-11-09 22:41:42

    这不是裸的kruskal吗

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    int n,m,k,f[1010];
    int ff(int x){return x==f[x]?x:f[x]=ff(f[x]);}
    struct edge{
    int l,r,v;
    }e[10010];
    bool cmp(edge a,edge b){return a.v<b.v;}
    int main()
    {
    scanf("%d%d%d",&n,&m,&k);
    int i,t=n,ans=0;
    for(i=1;i<=m;++i)scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].v);
    sort(e+1,e+m+1,cmp);
    for(i=1;i<=n;++i)f[i]=i;
    for(i=1;i<=m;++i)
    {
    if(t<=k)break;
    if(ff(e[i].l)!=ff(e[i].r))
    f[ff(e[i].l)]=ff(e[i].r),ans+=e[i].v,t--;
    }
    if(t==k)cout<<ans;else cout<<"No Answer";
    }

  • 0
    @ 2016-05-10 21:49:48

    评测结果
    编译成功

    Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
    Copyright (c) 1993-2015 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    foo.pas(54,28) Warning: Variable "k" does not seem to be initialized
    foo.pas(55,28) Warning: Variable "tot" does not seem to be initialized
    foo.pas(7,7) Note: Local variable "j" not used
    Linking foo.exe
    64 lines compiled, 0.0 sec, 28080 bytes code, 1268 bytes data
    2 warning(s) issued
    1 note(s) issued
    测试数据 #0: Accepted, time = 0 ms, mem = 924 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 924 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 920 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 924 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 924 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 924 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 924 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 920 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 924 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 924 KiB, score = 10
    Accepted, time = 15 ms, mem = 924 KiB, score = 100
    代码
    program p1234;
    type date=record
    x,y,dis:longint;
    end;
    var a:array [0..10000] of date;
    f:array [0..1000] of longint;
    i,j,n,m,k,tot,k1,k2,p:longint;

    procedure qsort(l,r:longint);
    var i,j,mid:longint;
    temp:date;
    begin
    i:=l;
    j:=r;
    mid:=a[(i+j) div 2].dis;
    repeat
    while a[i].dis<mid do inc(i);
    while a[j].dis>mid do dec(j);
    if i<=j then
    begin
    temp:=a[i];
    a[i]:=a[j];
    a[j]:=temp;
    inc(i);
    dec(j);
    end;
    until i>j;
    if i<r then qsort(i,r);
    if l<j then qsort(l,j);
    end;

    function sf(x:longint):longint;
    begin
    if x<>f[x] then sf:=sf(f[x])
    else sf:=f[x];
    f[x]:=sf;
    end;

    begin
    readln(n,m,p);
    for i:=1 to m do
    begin
    readln(a[i].x,a[i].y,a[i].dis);
    end;
    qsort(1,m);
    for i:=1 to n do f[i]:=i;
    for i:=1 to m do
    begin
    k1:=sf(a[i].x);
    k2:=sf(a[i].y);
    if k1<>k2 then
    begin
    f[k2]:=k1;
    inc(k);
    tot:=tot+a[i].dis;
    end;
    if k=n-p then
    begin
    writeln(tot);
    halt;
    end;
    end;
    writeln('No Answer');
    end.

  • 0
    @ 2016-03-23 21:39:50

    记录信息
    评测状态 Accepted
    题目 P1234 口袋的天空
    递交时间 2016-03-23 21:37:38
    代码语言 C++
    评测机 ShadowShore
    消耗时间 15 ms
    消耗内存 632 KiB
    评测时间 2016-03-23 21:37:39
    评测结果
    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:75:23: warning: unknown conversion type character 'l' in format [-Wformat=]
    printf("%lld", Answer);
    ^
    foo.cpp:75:23: warning: too many arguments for format [-Wformat-extra-args]
    测试数据 #0: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 628 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 624 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 624 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 632 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 632 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    Accepted, time = 15 ms, mem = 632 KiB, score = 100
    代码
    #include<cstdio>
    #include<algorithm>
    using namespace std;

    const int MaxN = 1000 + 10, MaxM = 10000 + 10;

    int N, M, K, A, B;
    long long Answer = 0;

    struct finduniteNode {
    int Parent;
    bool notRoot;
    }Node[MaxN];

    struct eageStruction {
    int From, Next, Cost;
    bool operator < (const eageStruction &X) const {
    return X.Cost > Cost;
    }
    }Eage[MaxM];

    int getInt() {
    int Return = 0;
    char Get = getchar();
    while(Get >= '0' && Get <= '9') {
    Return = Return * 10 + (Get - '0');
    Get = getchar();
    }
    return Return;
    }

    void Unite(const int &rootA, const int &rootB) {
    if(Node[rootA].Parent < Node[rootB].Parent) {
    Node[rootB].Parent += Node[rootA].Parent;
    Node[rootA].notRoot = 1;
    Node[rootA].Parent = rootB;
    }
    else {
    Node[rootA].Parent += Node[rootB].Parent;
    Node[rootB].notRoot = 1;
    Node[rootB].Parent = rootA;
    }
    }

    int Find(int Element, int theRoot, int parentNode) {
    theRoot = parentNode = Element;
    while(Node[theRoot].notRoot) theRoot = Node[theRoot].Parent;
    while(Element != theRoot) {
    parentNode = Node[Element].Parent;
    Node[Element].Parent = theRoot;
    Element = parentNode;
    }
    return theRoot;
    }

    int main() {
    N = getInt(); M = getInt(); K = getInt();
    if(M < N - K || N < K) {
    printf("No Answer"); return 0;
    }
    for(int i = 1; i <= N; ++i) Node[i].Parent = i;
    for(eageStruction *i = Eage + 1; i <= Eage + M; ++i) {
    i->From = getInt();
    i->Next = getInt();
    i->Cost = getInt();
    }
    sort(Eage + 1, Eage + M + 1);
    for(eageStruction *i = Eage + 1; i <= Eage + M && N > K; ++i) {
    A = Find(i->From, 0, 0); B = Find(i->Next, 0, 0);
    if(A != B) {
    Unite(A, B); --N;
    Answer = 1LL * (Answer + i->Cost);
    }
    }
    printf("%lld", Answer);
    return 0;
    }

  • 0
    @ 2016-02-28 17:34:47
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 1e4 + 10;
    
    int N, M, K, ans, tot;
    int fa[maxn];
    
    struct edge{ int x, y, v; } es[maxn];
    bool cmp(edge e1, edge e2) { return e1.v < e2.v; }
    
    int find(int x) { return x == fa[x] ? x : find(fa[x]); }
    
    void Kruskal() {
        sort(es + 1, es + 1 + M, cmp);
        for(int i = 1; i <= N; i++) fa[i] = i;
        for(int i = 1; i <= M && tot > K; i++) {
            int u = find(es[i].x), v = find(es[i].y);
            if(u != v) {
                fa[u] = v;
                ans += es[i].v;
                tot--;
            }
        }
    }
    
    int main() {
        scanf("%d%d%d", &N, &M, &K); tot = N;
        for(int i = 1; i <= M; i++) scanf("%d%d%d", &es[i].x, &es[i].y, &es[i].v);
        Kruskal();
        if(tot == K) printf("%d\n", ans);
        else printf("No Answer\n");
        
        return 0;
    }
    
  • 0
    @ 2016-02-16 22:57:29

    整整7次!终于A了!希望大家能一起不断的探索,不放弃地钻研,终会有结果的!!!

    讲解请看楼下楼下的xuxianbo

    附上我瞪大眼睛看了半小时才看出错误的代码:

    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    using namespace std;

    struct pathtype
    {
    int data;
    int a;
    int b;
    };
    int n , m , t , i , j , k , parent[1001] , ans = 0 , temp = 0;
    pathtype daolu[10001];

    int main()
    {
    scanf ("%d%d%d" , &n , &m , &t);
    if (n < t || m < n - t)
    {
    printf ("No answer");
    return 0;
    }
    for (i = 1; i <= m; i ++)
    {
    int x , y , z;
    scanf ("%d%d%d" , &x , &y , &z);
    daolu[i].data = z;
    daolu[i].a = x;
    daolu[i].b = y;
    }
    for (i = 1; i <= n; i ++)
    parent[i] = i;

    bool f = true;
    i = 1;
    while (f)
    {
    f = false;
    for (j = 1; j <= m - i; j ++)
    if (daolu[j].data > daolu[j + 1].data)
    {
    int x;
    x = daolu[j].data;
    daolu[j].data = daolu[j + 1].data;
    daolu[j + 1].data = x;
    x = daolu[j].a;
    daolu[j].a = daolu[j + 1].a;
    daolu[j + 1].a = x;
    x = daolu[j].b;
    daolu[j].b = daolu[j + 1].b;
    daolu[j + 1].b = x;
    f = true;
    }
    i ++;
    }

    for (i = 1; i <= m && temp < n - t; i ++)
    {
    if (parent[daolu[i].a] != parent[daolu[i].b])
    {
    temp ++;
    ans += daolu[i].data;
    for (j = 1; j <= n; j ++)
    if (parent[j] == parent[daolu[i].b] && j != daolu[i].b)
    parent[j] = parent[daolu[i].a];
    parent[daolu[i].b] = parent[daolu[i].a];
    }
    }
    if (temp < n - t)
    {
    printf ("No answer");
    return 0;
    }
    printf ("%d" , ans);
    return 0;
    }

  • 0
    @ 2015-10-11 09:18:01

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    struct dian{
    int from,to,money;
    }a[100001];
    int father[100001];
    int comp(const dian&x,const dian&y)
    {
    return x.money<y.money;
    }
    int find(int t)
    {
    if(father[t]!=t){
    father[t]=find(father[t]);
    return father[t];
    }
    else{
    return t;
    }
    }
    int main()
    {
    int n,m,k,i,j,total=0,sum=0;
    scanf("%d%d%d",&n,&m,&k);
    if(m<n-k||n<k){
    printf("No Answer");
    return 0;
    }
    for(i=1;i<=m;i++){
    scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].money);
    }
    sort(a+1,a+m+1,comp);
    for(i=1;i<=n;i++){
    father[i]=i;
    }
    for(i=1;i<=m;i++){
    int temp1=find(a[i].from);
    int temp2=find(a[i].to);
    if(temp1!=temp2){
    father[temp1]=temp2;
    sum+=a[i].money;
    total++;
    }
    if(total==n-k){
    break;
    }
    }
    printf("%d",sum);
    return 0;
    }

  • 0
    @ 2015-08-12 15:44:29

    代码。水过。。
    type arr=record
    l,r,z:longint;
    end;
    var a:array[1..10000]of arr;
    f:array[1..1000]of longint;
    i,n,m,k,ans,tot:longint;
    procedure qsort(l,r: longint);
    var i,j,x: longint;
    y:arr;
    begin
    i:=l;
    j:=r;
    x:=a[(l+r) div 2].z;
    repeat
    while a[i].z<x do inc(i);
    while x<a[j].z do dec(j);
    if not(i>j) then
    begin
    y:=a[i];
    a[i]:=a[j];
    a[j]:=y;
    inc(i);
    j:=j-1;
    end;
    until i>j;
    if l<j then qsort(l,j);
    if i<r then qsort(i,r);
    end;

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

    begin
    readln(n,m,k);
    tot:=n;
    for i:=1 to n do f[i]:=i;
    for i:=1 to m do
    readln(a[i].l,a[i].r,a[i].z);
    qsort(1,m);
    for i:=1 to m do
    begin
    if tot=k then
    begin
    writeln(ans);
    halt;
    end;
    if find(a[i].l)<>find(a[i].r) then
    begin
    f[find(a[i].l)]:=find(a[i].r);
    dec(tot);
    inc(ans,a[i].z);
    end;
    end;
    if tot=k then writeln(ans) else writeln('No Answer');
    end.

  • 0
    @ 2015-07-25 10:55:44

    我用并查集过的,貌似与kruscal没多大关系吧。。话说这题目看了好久才看懂
    program Project1;

    type rec = record
    x, y, cost: longint;
    end;

    var
    a: array[1..10000] of rec;
    id, size: array[1..1000] of longint;
    ans, total, n, m, k, i, idx, idy: longint;

    function find(k: longint): longint;

    begin
    while k <> id[k] do
    begin
    id[k] := id[id[k]];
    k := id[k];
    end;
    find := id[k];
    end;

    procedure union(x, y: longint);

    begin
    if size[x] >= size[y] then
    begin
    id[y] := x;
    size[x] := size[x] + size[y];
    end
    else
    begin
    id[x] := y;
    size[y] := size[y] + size[x];
    end;
    end;

    procedure qsort(l, r: longint);

    var
    i, j, x: longint;
    t: rec;
    begin
    i := l;
    j := r;
    x := a[(l + r) shr 1].cost;
    repeat
    while a[i].cost < x do
    Inc(i);
    while a[j].cost > x do
    Dec(j);
    if i <= j then
    begin
    t := a[i];
    a[i] := a[j];
    a[j] := t;
    Inc(i);
    Dec(j);
    end;
    until i > j;
    if i < r then
    qsort(i, r);
    if l < j then
    qsort(l, j);
    end;
    begin
    readln(n, m, k);
    for i := 1 to n do
    begin
    id[i] := i;
    size[i] := 1;
    end;
    for i := 1 to m do
    readln(a[i].x, a[i].y, a[i].cost);
    qsort(1, m);
    total := n;
    ans := 0;
    for i := 1 to m do
    begin
    idx := find(a[i].x);
    idy := find(a[i].y);
    if idx <> idy then
    begin
    union(idx, idy);
    Dec(total);
    ans := ans + a[i].cost;
    end;
    if total = k then
    break;
    end;
    if total > k then
    writeln('No Answer')
    else
    writeln(ans);
    readln;
    end.

  • 0
    @ 2015-07-02 11:06:31

    测试数据 #0: Accepted, time = 15 ms, mem = 548 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 548 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 552 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 552 KiB, score = 10

    测试数据 #5: Accepted, time = 15 ms, mem = 552 KiB, score = 10

    测试数据 #6: Accepted, time = 15 ms, mem = 548 KiB, score = 10

    测试数据 #7: Accepted, time = 15 ms, mem = 552 KiB, score = 10

    测试数据 #8: Accepted, time = 15 ms, mem = 548 KiB, score = 10

    测试数据 #9: Accepted, time = 15 ms, mem = 548 KiB, score = 10

    Accepted, time = 90 ms, mem = 552 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>

    using namespace std;

    long long n , m , k;
    long long i , j;
    long long now;
    long long ans;

    struct link
    {
    long long x , y , cost;
    };

    int cmp( link a , link b )
    {
    if( a.cost < b.cost )
    return 1;
    return 0;
    }

    int pre[ 10000 + 10 ];
    link a[ 10000 + 10 ];

    int find( int x )
    {
    if( pre[x] == x )
    return x;
    int a = x;
    x = find( pre[x] );
    pre[a] = x;
    return x;
    }

    void merge( long long x , long long y )
    {
    pre[ find( x ) ] = find( y );
    return;
    }

    int main()
    {
    scanf( "%lld %lld %lld" , &n , &m , &k );

    if( k > n || n - m > k )
    {
    printf( "No Answer\n" );
    return 0;
    }

    for( i = 1 ; i <= n ; i++ )
    pre[i] = i;
    for( i = 0 ; i < m ; i++ )
    scanf( "%lld %lld %lld" , &a[i].x , &a[i].y , &a[i].cost );

    sort( a , a + m , cmp );
    now = n;
    i = 0;
    ans = 0;
    while( now > k )
    {
    if( i >= m )
    {
    printf( "No Answer\n" );
    return 0;
    }
    if( find( a[i].x ) != find( a[i].y ) )
    {
    merge( a[i].x , a[i].y );
    now--;
    ans += a[i].cost;
    }
    i++;
    }
    printf( "%lld\n" , ans );
    return 0;
    }

  • 0
    @ 2015-02-05 10:23:13

    kruscal+quick sort+并查集
    #include<iostream>
    #include<string.h>
    #include<math.h>
    using namespace std;
    struct edge{
    int from, to, len;
    };
    edge e[10005];
    int node[1005];
    int size;
    int esize;
    int tree;
    void sort(int from, int to){
    if (from >= to)return;
    int i = from, j = to;
    edge k = e[from];
    while (true){
    while (e[j].len > k.len)j--;
    if (j == i)break;
    e[i] = e[j];
    e[j] = k;
    i++;
    while (e[i].len < k.len)i++;
    if (j == i)break;
    e[j] = e[i];
    e[i] = k;
    j--;
    }
    sort(from, i - 1);
    sort(i + 1, to);
    }
    int father(int n){
    while (node[n] != -1)n = node[n];
    return n;
    }
    void kruscal(){
    memset(node, -1, sizeof(node));
    int i, j;
    int ee = 0;
    int cost = 0;
    for (i = 0; i < esize&&ee < size - tree; i++){
    int ff = father(e[i].from);
    int tf = father(e[i].to);
    if (ff != tf){
    ee++;
    cost += e[i].len;
    node[ff]=tf;
    }
    }
    if (ee == size - tree){
    cout << cost << endl;
    }
    else
    cout << "No Answer" << endl;
    }
    int main(){
    freopen("in.txt", "r", stdin);
    cin >> size >> esize >> tree;
    int i;
    for (i = 0; i < esize; i++)
    cin >> e[i].from >> e[i].to >> e[i].len;
    sort(0, esize - 1);
    kruscal();
    return 0;
    }

  • 0
    @ 2014-11-05 09:42:23

    水题水过
    var x,y,l,i,n,m,k,ans,temp:longint;
    father,u,v,w:array[0..100000] of longint;

    function getfather(k:longint):longint;
    var tip:longint;
    begin
    if father[k]=k then exit(k);
    tip:=father[k];
    father[k]:=getfather(tip);
    getfather:=father[k];
    end;

    procedure qsort(a,b:longint);
    var i,j,x,temp:longint;
    begin
    i:=a;
    j:=b;
    x:=w[(i+j) div 2];
    repeat
    while w[i]<x do inc(i);
    while w[j]>x do dec(j);
    if i<=j then
    begin
    temp:=w[i];
    w[i]:=w[j];
    w[j]:=temp;
    temp:=u[i];
    u[i]:=u[j];
    u[j]:=temp;
    temp:=v[i];
    v[i]:=v[j];
    v[j]:=temp;
    inc(i);
    dec(j);
    end;
    until i>j;
    if i<b then qsort(i,b);
    if a<j then qsort(a,j);
    end;

    procedure kruskal;
    var i,t1,t2,tip:longint;
    begin
    tip:=0;
    for i:=1 to m do
    begin
    t1:=getfather(u[i]);
    t2:=getfather(v[i]);
    if t1<>t2 then
    begin
    father[t1]:=t2;
    ans:=ans+w[i];
    inc(tip);
    end;
    if tip=temp then break;
    end;
    if tip<temp then ans:=-1;
    end;

    begin
    //assign(input,'vj2.in');
    //assign(output,'vj2.out');
    //reset(input);
    //rewrite(output);
    readln(n,m,k);

    for i:=1 to m do
    begin
    readln(x,y,l);
    u[i]:=x;
    v[i]:=y;
    w[i]:=l;
    end;
    qsort(1,m);
    for i:=1 to n do father[i]:=i;
    temp:=n-k;
    kruskal;
    if ans<0 then writeln('No Answer')
    else
    writeln(ans);

    //close(input);
    //close(output);
    end.

信息

ID
1234
难度
5
分类
树结构 | 生成树 点击显示
标签
递交数
3503
已通过
1112
通过率
32%
被复制
4
上传者