HDU 3080 The plan of city rebuild(prim和kruskal)

By | 04月29日
Advertisement

The plan of city rebuild

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 616 Accepted Submission(s): 215

Problem Description

News comes!~City W will be rebuilt with the expectation to become a center city. There are some villages and roads in the city now, however. In order to make the city better, some new villages should be built and some old ones should be destroyed. Then the officers have to make a new plan, now you , as the designer, have the task to judge if the plan is practical, which means there are roads(direct or indirect) between every two villages(of course the village has not be destroyed), if the plan is available, please output the minimum cost, or output"what a pity!".

Input

Input contains an integer T in the first line, which means there are T cases, and then T lines follow.
Each case contains three parts. The first part contains two integers l(0<l<100), e1, representing the original number of villages and roads between villages(the range of village is from 0 to l-1), then follows e1 lines, each line contains three integers a, b, c (0<=a, b<l, 0<=c<=1000), a, b indicating the village numbers and c indicating the road cost of village a and village b . The second part first contains an integer n(0<n<100), e2, representing the number of new villages and roads(the range of village is from l to l+n-1), then follows e2 lines, each line contains three integers x, y, z (0<=x, y<l+n, 0<=z<=1000), x, y indicating the village numbers and z indicating the road cost of village x and village y. The third part contains an integer m(0<m<l+n), representing the number of deserted villages, next line comes m integers, p1,p2,…,pm,(0<=p1,p2,…,pm<l+n) indicating the village number.
Pay attention: if one village is deserted, the roads connected are deserted, too.

Output

For each test case, If all villages can connect with each other(direct or indirect), output the minimum cost, or output "what a pity!".

Sample Input

2 4 5 0 1 10 0 2 20 2 3 40 1 3 10 1 2 70 1 1 4 1 60 2 2 3 3 3 0 1 20 2 1 40 2 0 70 2 3 0 3 10 1 4 90 2 4 100 0

Sample Output

70 160

Author

wangjing

题目大意:先给你n1个点,m1条边,又给你n2个点,m2条边,然后告诉你有些点不需要,然后求剩下点的最

小生成树。反正光看题目就花了半小时,真不明白了,老路,新路,给边还分两次给。。

用了prim和kruskal两种算法来实现,中间还debug了蛮久。

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=3080

Prim算法:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF =1e8;
int mp[205][205];
int des[205];
int visi[205];
int low[205];  //更新最小值
int n;

int prim()
{
    int i,j;

    memset(visi,0,sizeof(visi));
    for(i=0;i<=200;i++)
        low[i]=INF;
    int ans=0,pos=-1;
    for(i=0;i<n;i++)
    {
        if(!des[i])
        {
            pos=i;
            break;
        }
    }

    if(pos==-1) return 0;

    for(i=0;i<=200;i++)
        low[i]=mp[pos][i];

    visi[pos]=1;
    int mi;
    for(i=0;i<n;i++)
    {
        mi=INF;
        int flag=0;
        for(j=0;j<n;j++)
        {
            if(des[j]) continue;
            if(!visi[j])
            {
                flag=1;
                if(low[j]<mi)
                {
                    mi=low[j];
                    pos=j;
                }
            }
        }

        if(mi==INF&&flag)
            return -1;
        if(!flag) return ans;
        ans+=mi;
        visi[pos]=1;
        for(j=0;j<n;j++)
            if(!visi[j])
                low[j]=min(low[j],mp[pos][j]);
    }
    return ans;
}

int main()
{
    int tes,i,j,res;
    scanf("%d",&tes);

    while(tes--)
    {
        int n1,m,u,v,val;
        scanf("%d%d",&n1,&m);

        for(i=0;i<=200;i++)
            for(j=0;j<=200;j++)
                mp[i][j]=INF;
        memset(des,0,sizeof(des));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            if(mp[u][v]>val)   //这个地方,边可能会多次给出,坑。。
            {
                mp[u][v]=val;
                mp[v][u]=val;
            }
        }
        int n2;
        scanf("%d%d",&n2,&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            if(mp[u][v]>val)
            {
                mp[u][v]=val;
                mp[v][u]=val;
            }
        }
        n=n1+n2;
        int t,x;
        scanf("%d",&t);
        for(i=0;i<t;i++)
        {
            scanf("%d",&x);
            des[x]=1;
        }

        res=prim();
        if(res==-1) puts("what a pity!");
        else printf("%d\n",res);
    }
    return 0;
}

Kruskal算法:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF =1e6;
const int maxn=205;

int n,m,t;   //总点数,总边数,desert的边数

int des[maxn];  //为1代表城市荒废
int fa[maxn];

struct Edge
{
    int from;
    int to;
    int val;
}edge[maxn*maxn];

int cmp(Edge p1,Edge p2)
{
    //if(des[p1.from]||des[p1.to]) return 0;
    //if(des[p2.from]||des[p2.to]) return 1;
    return p1.val<p2.val;
}

void init()
{
    for(int i=0;i<=200;i++)
        fa[i]=i;
}

int find1(int x)
{
    if(fa[x]!=x) fa[x]=find1(fa[x]);
    return fa[x];
}

void merge1(int p1,int p2)
{
    p1=find1(p1);
    p2=find1(p2);
    fa[p1]=p2;
}

int Kruskal()
{
    sort(edge,edge+m,cmp);
    int ans=0,ste=0;

    for(int i=0;i<m&&ste<n-t-1;i++)
    {
        int u=edge[i].from,v=edge[i].to,val=edge[i].val;
        if(des[u]||des[v]) continue;
        if(find1(u)!=find1(v))
        {
            ste++;
            ans+=val;
            merge1(u,v);
        }
    }

    if(ste==n-t-1) return ans;
    return -1;
}

int main()
{
    int tes,i,j,res;
    scanf("%d",&tes);

    while(tes--)
    {
        int n1,m1,u,v,val,n2,m2;
        scanf("%d%d",&n1,&m1);

        memset(des,0,sizeof(des));

        for(i=0;i<m1;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            edge[i].from=u;
            edge[i].to=v;
            edge[i].val=val;
        }

        scanf("%d%d",&n2,&m2);
        n=n1+n2;
        m=m1+m2;

        for(i=m1;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            edge[i].from=u;
            edge[i].to=v;
            edge[i].val=val;
        }

        int x;
        scanf("%d",&t);
        for(i=0;i<t;i++)
        {
            scanf("%d",&x);
            des[x]=1;
        }

        init();
        res=Kruskal();

        //cout<<n<<" :n"<<endl;
        if(res==-1) puts("what a pity!");
        else printf("%d\n",res);
    }
    return 0;
}

Similar Posts:

  • hdoj 3080 The plan of city rebuild(prim)

    [题目大意]:给出一幅图,再这幅图上加上一幅图,再删去几个点,求最小生成树.求不到输出"what a pity!" [解题思路]:prim直接写.一时没注意.原来有重边. [代码]: #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #inc

  • hdu3080 The plan of city rebuild

    简单最小生成树. 就是读题很纠结,什么原有的路,新建的路,删除的村庄. 总之,所有给的边都加上,删除点的操作就是把与该点相连的所有边删除(边权变成inf就是了),然后求最小生成树. 用kruskal比较方便判断不连通的情况. #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define inf 0x3f3f3f3f using namespace std;

  • 【图论】信手拈来的Prim,Kruskal和Dijkstra

    关于三个简单的图论算法 prim,dijkstra和kruskal三个图论的算法,初学者容易将他们搞混,所以放在一起了. prim和kruskal是最小生成树(MST)的算法,dijkstra是单源最短路径的算法. prim 最小生成树prim算法采用了贪心策略:把点分成两个集合,A为已被处理(已经在最小生成树中)的顶点,B为待处理的顶点,(A,B)也就是一个割.若边(u,v)满足u∈A,v∈B,那么(u,v)就是通过割(A,B)的一条边. 很自然的,会有一定数量的边会通过该割,其中权重最小的边

  • 畅通工程再续 HDU杭电1875 【Kruscal算法 || Prim】

    Problem Description 相信大家都听说一个"百岛湖"的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的小岛时都要通过划小船来实现.现在政府决定大力发展百岛湖,发展首先要解决的问题当然是交通问题,政府决定实现百岛湖的全畅通!经过考察小组RPRush对百岛湖的情况充分了解后,决定在符合条件的小岛间建上桥,所谓符合条件,就是2个小岛之间的距离不能小于10米,也不能大于1000米.当然,为了节省资金,只要求实现任意2个小岛之间有路通即可.其中桥的价格为 100元/米.

  • hdu 5352 MZL&amp;#39;s City 【二分图】

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5352 题意: 给你n,m,k 表示n个建筑 m次操作,修复操作每次最多修复k个建筑. 有三种操作 1.修复x点周围建筑(<=k) 2.x,y建筑间建边 3.x,y间删边 修复建筑时候拆点建图.反着求最大匹配,保证字典序最小. 代码: #include <stdio.h> #include <ctime> #include <math.h> #include <l

  • HDU 3371 Prim或kruskal实现

    Connect the Cities Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16619 Accepted Submission(s): 4256 Problem Description In 2100, since the sea level rise, most of the cities disappear. Though so

  • hdu 4671——Backup Plan

    #include<iostream> #include<cstdio> #include<cstring> using namespace std; int num[300]; int n,m; void solve1() { int i; for(i=1;i<m;i++) { printf("%d %d",i,n); for(int j=1;j<n;j++) if(j!=i) printf(" %d",j); pri

  • HDU 5352 MZL&amp;#39;s City (2015 Multi-University Training Contest 5)

    题目大意: 一个地方的点和道路在M年前全部被破坏,每年可以有三个操作, 1.把与一个点X一个联通块内的一些点重建,2.连一条边,3.地震震坏一些边,每年最多能重建K个城市,问最多能建多少城市,并输出操作要让字典序最小 思路: trivial:显然每年向当年可以建的城市连边,每年可以匹配最多K个城市,嗯,很明显的网络流思路,可这样方案数不太好输出 full:再仔细想想这就是多对一的多重匹配,跑一跑匈牙利就可以,K个城市可以拆点,当然简单的方法直接跑K次也可以(想一想为什么) 为了字典序最小,我们要

  • 杭电oj1875畅通工程再续(prim VS kruskal) 模板题

    畅通工程再续 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 20185 Accepted Submission(s): 6341 Problem Description 相信大家都听说一个"百岛湖"的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的小岛时都要通过划小船来实现.现在政府决定大力发展百岛湖,发展首先要解决的问题

  • 数据结构 19 图 最小连通图 prim与Kruskal算法

    Prim算法 顶点 #include <stdio.h> #include <stdlib.h> #define VNUM 9 #define MV 65536 int P[VNUM]; // 记录了顶点的索引 int Cost[VNUM]; // 保存了某个顶点边的权值 int Mark[VNUM]; // 记录某个顶点是否被标记 int Matrix[VNUM][VNUM] = { {0, 10, MV, MV, MV, 11, MV, MV, MV}, {10, 0, 18,

Tags: