hdoj畅通工程系列题目（accept代码）

àì夳堔傛蜴生んèń 2022-08-04 04:28 106阅读 0赞

1232 畅通工程

#include<stdio.h>
    int a[1005];
    int find(int x){
        int r=x;
        while(r!=a[r])
            r=a[r];
        int i=x,j;      //--
        while(i!=r){    //  |
            j=a[i];     //  |-压缩路径
            a[i]=r;     //  |-可有可无
            i=j;        //  |
        }               //--
        return r;
    }
    void join(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx!=fy)
            a[fx]=fy;
    }
    int main(){
        int n,m,i,j,x,y,ans;
        while(scanf("%d%d",&n,&m),n){
            ans=0;
            for(i=1;i<=n;i++)
                a[i]=i;
            for(i=0;i<m;i++){
                scanf("%d%d",&x,&y);
                join(x,y);
            }
            for(i=1;i<=n;i++)
                if(a[i]==i)
                    ans++;
            printf("%d\n",ans-1);
        }
        return 0;
    }

1233 还是畅通工程

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int pre[105];
    int n,m;
    
    struct ak{
        int s,c,l;
    }a[5010];
    
    int cmp(ak k,ak g){
        return k.l<g.l;
    }
    
    void init(){
        for(int i=1;i<=n;i++)
            pre[i]=i;
    }
    
    int find(int x){
        int r=x;
        while(r!=pre[r])
            r=pre[r];
        return r;
    }
    
    bool join(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx!=fy){
            pre[fx]=fy;
            return true;
        }
        return false;
    }
    
    int main(){
        while(scanf("%d",&n),n){
            m=n*(n-1)/2;
            for(int i=0;i<m;i++)
                scanf("%d%d%d",&a[i].s,&a[i].c,&a[i].l);
            sort(a,a+m,cmp);
            init();
            int an=0;
            for(int i=0;i<m;i++){
                if(join(a[i].s,a[i].c))
                    an+=a[i].l;
            }
            printf("%d\n",an);
        }
        return 0;
    }

1863 畅通工程

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int per[1010];
    void init(int n){
        for(int i=1;i<=n;i++)
            per[i]=i;
    }
    
    struct node{
        int s,c,l;
    }a[10050];
    
    int cmp(node k,node g){
        return k.l<g.l;
    }
    
    int find(int x){
        int r=x;
        while(r!=per[r])
            r=per[r];
        return r;
    }
    
    bool join(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx!=fy){
            per[fx]=fy;
            return true;
        }
        return false;
    }
    
    int main(){
        int n,m,i,j;
        while(scanf("%d",&n),n){
            scanf("%d",&m);
            init(m);
            for(i=0;i<n;i++)
                scanf("%d%d%d",&a[i].s,&a[i].c,&a[i].l);
            sort(a,a+n,cmp);
            int total=0,sum=0;
            for(i=0;i<n;i++){
                if(join(a[i].s,a[i].c)){
                    total++;
                    sum+=a[i].l;
                }
                if(total==m-1)
                    break;
            }
            if(total==m-1)
                printf("%d\n",sum);
            else
                printf("?\n");
        }
        return 0;
    }

1874 畅通工程续

#include<stdio.h>
    #include<string.h>
    #define M 0x3f3f3f3f
    int n,m,k,t;
    int a[201][201];
    int dis[201];
    int vis[201];
    int minn(int a,int b){
        return a>b?b:a;
    }
    void dijkstra(){
        for(int i=0;i<n;i++){
            dis[i]=M;
            vis[i]=0;
        }
        dis[k]=0;
        while(1){
            int v=-1;
            for(int i=0;i<n;i++)
                if(!vis[i]&&(v==-1||dis[i]<dis[v]))
                    v=i;
            if(v==-1)
                break;
            vis[v]=1;
            for(int i=0;i<n;i++){
                dis[i]=minn(dis[i],dis[v]+a[v][i]);
            }
        }
        if(dis[t]==M)
            printf("-1\n");
        else
            printf("%d\n",dis[t]);
    }
    int main(){
        int i,s,c,l,j;
        while(scanf("%d%d",&n,&m)!=EOF){
            for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                    a[i][j]=M;
            for(i=0;i<m;i++){
                scanf("%d%d%d",&s,&c,&l);
                if(a[s][c]>l){
                    a[s][c]=l;
                    a[c][s]=l;    
                }
            }
            scanf("%d%d",&k,&t);
            dijkstra();
        }
        return 0;
    }

1875 畅通工程再续

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<math.h>
    using namespace std;
    #define M 0x3f3f3f3f
    int n,m;
    int x[101],y[101];
    double map[101][101];
    
    
    void prim(){
        int v[101],pos,i,j;
        double total=0,dis[101],min=0;
        memset(v,0,sizeof(v));
        v[1]=1;
        for(i=1;i<=n;i++)
            if(i!=1)
                dis[i]=map[1][i];
        dis[1]=0;
        pos=1;
        for(i=2;i<=n;i++){
            min=M;
            for(j=1;j<=n;j++){
                if(!v[j]&&dis[j]<min){
                    min=dis[j];
                    pos=j;
                }
            }
            if(min==M){
                printf("oh!\n");
                return ;
            }
            total+=min;
            v[pos]=1;
            for(j=1;j<=n;j++){
                if(!v[j]&&dis[j]>map[pos][j])
                    dis[j]=map[pos][j];
            }
        }
        printf("%.1lf\n",total*100.0);
        return ;
    }
    
    int main(){
        int t,i,j;
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n);
            for(i=1;i<=n;i++)
                scanf("%d%d",&x[i],&y[i]);
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++){
                    map[i][j]=map[j][i]=sqrt(1.0*((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
                    if(map[i][j]>1000||map[i][j]<10)
                        map[i][j]=map[j][i]=M;
                }
            prim();
        }
        return 0;
    }

1879继续畅通工程

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int n,m;
    int pre[101];
    
    struct ak{
        int s,c,l;
    }a[10000],b[10000];
    
    void init(){
        for(int i=0;i<=n;i++)
            pre[i]=i;
    }
    
    int cmp(ak d,ak s){
        return d.l<s.l;
    }
    
    int find(int x){
        int r=x;
        while(r!=pre[r])
            r=pre[r];
        int i=x,j;
        if(i!=r){
            j=pre[i];
            pre[i]=r;
            i=j;
        }
        return r;
    }
    
    bool join(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx!=fy){
            pre[fx]=fy;
            return true;
        }
        return false;
    }
    
    int main(){
        while(scanf("%d",&n),n){
            int i,j,g,w=0,q=0;
            int x,y,z,k;
            g=n*(n-1)/2;
            for(i=0;i<g;i++){
                scanf("%d%d%d%d",&x,&y,&z,&k);
                if(k==0){
                    a[q].s=x;
                    a[q].c=y;
                    a[q++].l=z;
                }
                else{
                    b[w].s=x;
                    b[w].c=y;
                    b[w++].l=z;
                }
            }
            init();
            sort(a,a+q,cmp);
            int total=0;
            for(i=0;i<w;i++)
                join(b[i].s,b[i].c);
            for(i=0;i<q;i++)
                if(join(a[i].s,a[i].c)){
                    total+=a[i].l;
                }
            printf("%d\n",total);
        }
        return 0;
    }