Prim和Kruskal求最小生成树

喜欢ヅ旅行 2022-06-06 07:43 146阅读 0赞

前两天TCP/IP协议课上,老师谈到图论中的几个简单算法,发现自己不是很熟练,所以马上挂了一套MST的题目来练练手,题目很简单,但由于课程比较多,所以还有三个题没来得及刷,同时在此%一波典

假设给出了一个图G<V,E>

首先是Prim算法,基于贪心的思想,任选一个点形成一棵树,然后不断的从剩下的点中挑出距离这棵树中任意一个点距离最小的点,不断的重复这个操作,直到n个点都加入到树中形成最小生成树.时间复杂度为O(|V|^2)

[点我看Prim详解][Prim]

关于Kruskal算法,也是基于贪心的思想,同时利用了并查积,先选出一条最小的边,这个边形成一个边的集合,然后再选出一条最小的边,如果这条边的两个点的祖先不是同一个的话,把这条边加入到边的集合中,直到找到n-1条边为止.时间复杂度为O(ElogE).

[点我看Kruskal详解][Kruskal]

从时间复杂度来看,Prim适用于点比较少的图,Kruskal适合边较少的图.

最小生成树基础题:

[HDU-1102 Constructing Roads][]

/*Prim求最小生成树*/
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    #define inf 0x3f3f3f3f
    const int maxn = 1e2+10;
    int n,q;
    int mp[maxn][maxn];
    int lowcost[maxn];//表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST
    int mst[maxn];//表示对应lowcost[i]的起点,即说明边<mst[i],i>是MST的一条边,当mst[i]=0表示起点i加入MST
    
    int Prim()
    {
        //初始化lowcost和mst
        mst[1] = 0;
        lowcost[1] = -1;//先把第一个点加到生成树里面
        for( int i = 2; i<= n; i++)
        {
            lowcost[i] = mp[1][i];//初始化以i为终点的最小权值
            mst[i] = 1;//以哪个点为起点才能得到的最小权值
        }
    
        int mn,mnid;//当前边的最小权值,加入的点的编号
        int sum = 0;//最小权值和
        for( int i = 2; i <= n; i++)
        {
            mn = inf;
            mnid = 0;
            for( int j = 2; j <= n; j++)
            {
                // printf("j=%d lowcost[j]=%d mn=%d\n",j,lowcost[j],mn);
                if( lowcost[j] < mn && lowcost[j] != -1)//当前权值小且没有加入到树中
                {
                    mn = lowcost[j];
                    mnid = j;
                }
            }
            sum += mn;
            // printf("sum=%d mnid=%d\n",sum,mnid);
            lowcost[mnid] = -1;
            for( int j = 2; j <= n; j++)
            {
                if( mp[mnid][j] < lowcost[j])
                {
                    lowcost[j] = mp[mnid][j];
                    mst[j] = mnid;
                }
            }
    
        }
        return sum;
    }
    
    int main()
    {
        while( ~scanf("%d",&n))
        {
            for( int i = 1; i <= n; i++)
                for( int j = 1; j <= n; j++)
                    scanf("%d",&mp[i][j]);
            scanf("%d",&q);
            while( q--)
            {
                int u,v;
                scanf("%d%d",&u,&v);
                mp[u][v] = mp[v][u] = 0;//这是别人已经修好了的路,要用的话就是零消费
            }
    
            int ans = 0;
            ans = Prim();
            printf("%d\n",ans);
        }
    
        return 0;
    }

[HDU-2122 Ice\_cream’s world III][HDU-2122 Ice_cream_s world III]

/*Prim求最小生成树*/
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    #define inf 0x3f3f3f3f
    const int maxn = 1e3+10;
    const int maxm = 1e4+10;
    int n,m;
    int mp[maxn][maxn];
    int lowcost[maxn];
    int mst[maxn];
    
    int Prim()
    {
        //初始化
        lowcost[0] = -1;
        mst[0] = 0;
        for( int i = 1; i < n; i++)
        {
            lowcost[i] = mp[0][i];
            mst[i] = 0;
        }
    
        int mn,id;
        int sum = 0;
        for( int i = 1; i < n; i++)
        {
            mn = inf;
            id = 0;
            for( int j = 1; j < n; j++)
            {
                if( lowcost[j] < mn && lowcost[j] != -1)
                {
                    mn = lowcost[j];
                    id = j;
                }
            }
    
            sum += lowcost[id];
            lowcost[id] = -1;
            for( int j = 1; j < n; j++)
            {
                if( mp[id][j] < lowcost[j])
                {
                    lowcost[j] = mp[id][j];
                    mst[j] = id;
                }
            }
        }
    
        return sum;
    }
    
    int main()
    {
        int flak = false;
        while( ~scanf("%d%d",&n,&m))
        {
            mem(mp,inf);
            int u,v,x;
            for( int i = 1; i <= m; i++)
            {
                scanf("%d%d%d",&u,&v,&x);
                if( u != v)//存在重边的情况
                {
                    mp[u][v] = min(mp[u][v],x);
                    mp[v][u] = min(mp[v][u],x);
                }
            }
    
            int ans = Prim();
            int cnt = 0;
            for( int i = 0; i < n; i++)
                if( lowcost[i] == -1)
                    cnt++;
            if( cnt != n)
                puts("impossible");
            else
                printf("%d\n",ans);
            puts("");
        }
    
        return 0;
    }

[HDU-1233 还是畅通工程][HDU-1233]

/*Prim*/
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    #define inf 0x3f3f3f3f
    const int maxn = 1e2+10;
    int n;
    int mp[maxn][maxn];
    int lowcost[maxn];
    int mst[maxn];
    
    int Prim()
    {
        lowcost[1] = -1, mst[1] = 0;
        for( int i = 2; i <= n; i++)
            lowcost[i] = mp[1][i], mst[i] = 1;
    
        int mn, id;
        int sum = 0;
        for( int i = 2; i <= n; i++)
        {
            mn = inf;
            id = 0;
            for( int j = 2; j <= n; j++)
            {
                if( lowcost[j] < mn && lowcost[j] != -1)
                {
                    mn = lowcost[j];
                    id = j;
                }
            }
    
            sum += lowcost[id];
            lowcost[id] = -1;
            for( int j = 2; j <= n; j++)
            {
                if( mp[id][j] < lowcost[j])
                {
                    lowcost[j] = mp[id][j];
                    mst[j] = id;
                }
            }
        }
        return sum;
    }
    
    int main()
    {
        while( ~scanf("%d",&n) && n)
        {
            mem(mp,inf);
            int m = n*(n-1)/2;
            int u,v,x;
            for( int i = 1; i <= m; i++)
            {
                scanf("%d%d%d",&u,&v,&x);
                mp[u][v] = x;
                mp[v][u] = x;
            }
    
            int ans = Prim();
            printf("%d\n",ans);
        }
    
        return 0;
    }

[HDU-1863 畅通工程][HDU-1863]

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    #define inf 0x3f3f3f3f
    const int maxn = 1e2+10;
    int n,m;
    int mp[maxn][maxn];
    int lowcost[maxn];
    int mst[maxn];
    
    int Prim()
    {
        lowcost[1] = -1;
        mst[1] = 0;
        for( int i = 2; i <= m; i++)
        {
            lowcost[i] = mp[1][i];
            mst[i] = 1;
        }
    
        int mn,id;
        int sum = 0;
        for( int i = 2; i <= m; i++)
        {
            mn = inf;
            id = 0;
            for( int j = 2; j <= m; j++)
            {
                if( lowcost[j] < mn && lowcost[j] != -1)
                {
                    mn = lowcost[j];
                    id = j;
                }
            }
    
            sum += lowcost[id];
            lowcost[id] = -1;
            for( int j = 2; j <= m; j++)
            {
                if( mp[id][j] < lowcost[j])
                {
                    lowcost[j] = mp[id][j];
                    mst[j] = id;
                }
            }
        }
        return sum;
    }
    
    int main()
    {
        while( ~scanf("%d%d",&n,&m) && n)
        {
            mem(mp,inf);
            int u,v,x;
            for( int i = 0; i < n; i++)
            {
                scanf("%d%d%d",&u,&v,&x);
                mp[u][v] = min(mp[u][v],x);
                mp[v][u] = min(mp[v][u],x);
            }
    
            int ans = Prim();
            int cnt = 0;
            for( int i = 1; i <= m; i++)
            {
                if( lowcost[i] == -1)
                    cnt++;
            }
            if( cnt != m)
                puts("?");
            else
                printf("%d\n",ans);
        }
    
        return 0;
    }

[HDU-1875 畅通工程再续][HDU-1875]

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    #define inf 1e20
    #define eps 1e-8
    const int maxn = 1e2+10;
    int n;
    double mp[maxn][maxn];
    double lc[maxn];
    int vis[maxn];
    struct Point{
        int x,y;
        Point(){}
        Point( int _x, int _y)
        {
            x = _x, y = _y;
        }
    };
    Point p[maxn];
    
    int sgn( double x)
    {
        if( fabs(x) < eps)
            return 0;
        if( x < 0)
            return -1;
        return 1;
    }
    
    int sqr( int x)
    {
        return x*x;
    }
    
    double dist( Point a, Point b)
    {
        return sqrt(1.0*(sqr(a.x-b.x)+sqr(a.y-b.y)));
    }
    
    double Prim()
    {
        mem(vis,0);
        vis[1] = 1;
        for( int i = 2; i <= n; i++)
            lc[i] = mp[1][i];
    
        double mn;
        int id;
        double sum = 0;
        for( int i = 2; i <= n; i++)
        {
            mn = inf;
            id = 0;
            for( int j = 2; j <= n; j++)
            {
                if( !vis[j] && lc[j] < mn)
                {
                    mn = lc[j];
                    id = j;
                }
            }
            sum += mn;
            vis[id] = 1;
            for( int j = 2; j <= n; j++)
            {
                if( !vis[j] && mp[id][j] < lc[j])
                    lc[j] = mp[id][j];
            }
        }
        return sum;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while( T--)
        {
            scanf("%d",&n);
            for( int i = 1; i <= n; i++)
                scanf("%d%d",&p[i].x,&p[i].y);
    
            for( int i = 1; i <= n; i++)
            {
                for( int j = 1; j <= n; j++)
                {
                    mp[i][j] = inf;
                    double dis = dist(p[i],p[j]);
                    if( sgn(dis-10.0) >= 0 && sgn(dis-1000.0) <= 0)
                        mp[i][j] = dis;
                }
            }
            double ans = Prim();
            if( ans >= inf)
                puts("oh!");
            else
                printf("%.1f\n",ans*100);
        }
    
        return 0;
    }

[HDU-3371 Connect the Cities][]

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    #define inf 0x3f3f3f3f
    const int maxn = 5e2+10;
    int n,m,k;
    int mp[maxn][maxn];
    int con[maxn];
    int lc[maxn];
    bool vis[maxn];
    int ans;
    
    void Prim()
    {
        mem(vis,0);
        vis[1] = 1;
        for( int i = 2; i <= n; i++)
            lc[i] = mp[1][i];
    
        int pos = 1;
        ans = 0;
        for( int i = 2; i <= n; i++)
        {
            int mn = inf;
            for( int j = 2; j <= n; j++)
            {
                if( !vis[j] &&  lc[j] < mn)
                {
                    mn = lc[j];
                    pos = j;
                }
            }
    
            ans += mn;
            if( mn == inf)
                return;
            vis[pos] = 1;
    
            for( int j = 2; j <= n; j++)
            {
                if( !vis[j] && mp[pos][j] < lc[j])
                    lc[j] = mp[pos][j];
            }
        }
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while( T--)
        {
            mem(mp,inf);
            scanf("%d%d%d",&n,&m,&k);
            int u,v,x;
            for( int i = 0; i < m; i++)
            {
                scanf("%d%d%d",&u,&v,&x);
                mp[u][v] = min(mp[u][v],x);
                mp[v][u] = min(mp[v][u],x);
            }
    
            while( k--)
            {
                int t;
                scanf("%d",&t);
                for( int i = 0; i < t; i++)
                    scanf("%d",&con[i]);
                for( int i = 0; i < t; i++)
                    for( int j = i+1; j < t; j++)
                        mp[con[i]][con[j]] = mp[con[j]][con[i]] = 0;
            }
    
            Prim();
            if( ans > inf)
                puts("-1");
            else
                printf("%d\n",ans);
        }
    
    
        return 0;
    }

[HDU-1301 Jungle Roads][]

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    #define inf 0x3f3f3f3f
    const int maxn = 1e2+10;
    int n;
    int mp[maxn][maxn];
    int lc[maxn];
    bool vis[maxn];
    int ans;
    
    void Prim()
    {
        mem(vis,0);
        vis[1] = 1;
        for( int i = 2; i <= n; i++)
            lc[i] = mp[1][i];
    
        int pos = 1;
        ans = 0;
        for( int i = 2; i <= n; i++)
        {
            int mn = inf;
            for( int j = 2; j <= n; j++)
            {
                if( !vis[j] &&  lc[j] < mn)
                {
                    mn = lc[j];
                    pos = j;
                }
            }
    
            ans += mn;
            if( mn == inf)
                return;
            vis[pos] = 1;
    
            for( int j = 2; j <= n; j++)
            {
                if( !vis[j] && mp[pos][j] < lc[j])
                    lc[j] = mp[pos][j];
            }
        }
    }
    
    int main()
    {
        while( ~scanf("%d",&n) && n)
        {
            mem(mp,inf);
            for( int i = 1; i < n; i++)
            {
                getchar();
                char ch;
                int u,v,x;
                scanf("%c",&ch);
                u = ch-'A'+1;
                int t;
                scanf("%d",&t);
                for( int i = 0; i < t; i++)
                {
                    getchar();
                    scanf("%c%d",&ch,&x);
                    v = ch-'A'+1;
                    mp[u][v] = min(mp[u][v],x);
                    mp[v][u] = min(mp[v][u],x);
                }
            }
            // for( int i = 1; i <= n; i++)
            // {
            //     for( int j = 1; j <= n; j++)
            //     {
            //         if( mp[i][j] == inf)
            //             printf(" -1");
            //         else
            //             printf("%3d",mp[i][j]);
            //     }
            //     puts("");
            // }
            Prim();
            printf("%d\n",ans);
        }
    
        return 0;
    }

[HDU-1162 Eddy's picture][HDU-1162 Eddy_s picture]

/*Kruskal*/
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    #define inf 1e20;
    const int maxn = 1e2+10;
    const int maxm = 1e4+10;
    int n;
    struct Point{
        double x,y;
    };
    Point p[maxn];
    struct Edge{
        int a,b;
        double dis;
        Edge(){}
        Edge( int _a, int _b, double _dis)
        {
            a = _a, b = _b, dis = _dis;
        }
    };
    Edge e[maxm];
    int sz;//边的条数
    double ans;
    int pre[maxn];
    
    void Init()
    {
        for( int i = 0; i < n; i++)
            pre[i] = i;
    }
    
    double sqr( double x)
    {
        return x*x;
    }
    
    double dist( Point p0, Point p1)
    {
        return sqrt(sqr(p0.x-p1.x)+sqr(p0.y-p1.y));
    }
    
    bool cmp( Edge e0, Edge e1)
    {
        return e0.dis < e1.dis;
    }
    
    int Find( int x)
    {
        if( x == pre[x])
            return x;
        return pre[x] = Find(pre[x]);
    }
    
    void Union( int x, int y)
    {
        int px = Find(x);
        int py = Find(y);
        if( px != py)
            pre[px] = py;
    }
    
    void Kruskal()
    {
        sort(e,e+sz,cmp);
        int edge = 0;
        for( int i = 0; i < sz && edge != n-1; i++)
        {
            if( Find(e[i].a) != Find(e[i].b))
            {
                Union(e[i].a,e[i].b);
                ans += e[i].dis;
                edge++;
            }
        }
    }
    
    int main()
    {
        while( ~scanf("%d",&n))
        {
            for( int i = 0; i < n; i++)
                scanf("%lf%lf",&p[i].x,&p[i].y);
            sz = 0;
            for( int i = 0; i < n; i++)
            {
                for( int j = i+1; j < n; j++)
                {
                    double dis = dist(p[i],p[j]);
                    e[sz++] = Edge(i,j,dis);
                }
            }
    
            Init();
            ans = 0;
            Kruskal();
            printf("%.2f\n",ans);
        }
    
        return 0;
    }

[Prim]: http://blog.csdn.net/yeruby/article/details/38615045
[Kruskal]: http://blog.csdn.net/luomingjun12315/article/details/47700237
[HDU-1102 Constructing Roads]: http://acm.hdu.edu.cn/showproblem.php?pid=1102
[HDU-2122 Ice_cream_s world III]: http://acm.hdu.edu.cn/showproblem.php?pid=2122
[HDU-1233]: http://acm.hdu.edu.cn/showproblem.php?pid=1233
[HDU-1863]: http://acm.hdu.edu.cn/showproblem.php?pid=1863
[HDU-1875]: http://acm.hdu.edu.cn/showproblem.php?pid=1875
[HDU-3371 Connect the Cities]: http://acm.hdu.edu.cn/showproblem.php?pid=3371
[HDU-1301 Jungle Roads]: http://acm.hdu.edu.cn/showproblem.php?pid=1301
[HDU-1162 Eddy_s picture]: http://acm.hdu.edu.cn/showproblem.php?pid=1162