图论问题(2) : hdu 1102

题目转自hdu 1102，题目传送门

题目大意：

输入一个n*n的邻接矩阵，其中i行j列代表从i到j的路径的长度

然后又m条路已经帮你修好了，求最短要修多长的路才能使所有村庄连接

不难看出，这道题就是标准的最小生成树模板，多水啊

解题思路

虽然很水，但本人还是调了近1h才把代码调好......

下面介绍一下解决最小生成树的两个方法：

Prim 和 Kruskal

一，Prim（不懂的点这里）

Prim的思想和dijkstra的想法很想（如果不知道dijkstra算法的请点这里）

那么Prim的复杂度在为优化之前是O(n²)，还是很慢的（虽然这道题能过）

既然这样，那这道题该怎么用Prim解呢？

思考了近10min后我想到了一个绝妙的方法，但是这里地方太小写不下

既然已经有建好了的，那我们肯定要用他已经建好的

所以，我们在输入时做一个预处理

将所有已经建过的路的距离化为0，然后再跑一遍Prim就行了

预处理代码如下：

for(int i=;i<=m;i++)

{

    int x,y;

    scanf("%d%d",&x,&y);

    g[x][y]=g[y][x]=;

}

p.s.：g为邻接矩阵

然后在花15min打一遍Prim算法就可以愉快地AC了

AC代码如下：

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#define inf 2147483647

using namespace std;

bool vis[];

int n,m,cnt,ans,u;

int dis[];

int g[][];

void init()

{

    ans=cnt=;

    memset(vis,false,sizeof(vis));

    memset(dis,0x7f,sizeof(dis));

    return ;

}

void pirm()

{

    dis[]=;

    while(true)

    {

        u=;

        for(int i=;i<=n;i++)

            if(!vis[i] && (dis[i]<dis[u])) u=i;

        if(u==) return ;

        vis[u]=true;

        ans+=dis[u];

        for(int i=;i<=n;i++) dis[i]=min(dis[i],g[u][i]);

    }

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        init();

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                scanf("%d",&g[i][j]);

        scanf("%d",&m);

        for(int i=;i<=m;i++)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            g[x][y]=g[y][x]=;

        }

        pirm();

        printf("%d\n",ans);

    }

    return ;

}

接下来看Kruskal......

二，Kruskal（不懂的点这里）

Kruskal中将用到hdu 1198中的并查集（点此转到我的的博客：图论问题(1)：hdu 1198）

Kruskal主要就是把边按边权从小到大排序

在通过并查集检查目前最小的边的两端是否在同一集合中

若是，则跳过这条边

否则就把他们归为一个集合

这里只需要提前作这一步骤就行了

预处理代码如下：

for(int i=;i<=m;i++)

{

    int x,y;

    scanf("%d%d",&x,&y);

    Union(x,y);

}

p.s.：其中Union为合并函数

然后就花个20min写完模板就可以愉快地AC了

AC代码如下：

#include<iostream>

#include<stdio.h>

#include<algorithm>

using namespace std;

struct edge

{

    int from,to,w;

    bool operator<(const edge &a)const

    {

        return w<a.w;

    }

}e[];

int n,m,cnt,ans;

int fa[];

void init()

{

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

    cnt=ans=;

    return ;

}

int find_fa(int x)

{

    if(x==fa[x]) return x;

    else

    {

        fa[x]=find_fa(fa[x]);

        return fa[x];

    }

    return ;

}

void Union(int x,int y)

{

    x=find_fa(x);

    y=find_fa(y);

    if(x<y) fa[y]=x;

    else fa[x]=y;

    return ;

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        init();

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

            {

                scanf("%d",&e[cnt].w);

                e[cnt].from=i;e[cnt].to=j;

                cnt++;

            }

        scanf("%d",&m);

        for(int i=;i<=m;i++)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            Union(x,y);

        }

        sort(e,e+cnt);

        for(int i=;i<cnt;i++)

            if(find_fa(e[i].from)!=find_fa(e[i].to))

            {

                Union(e[i].from,e[i].to);

                ans+=e[i].w;

            }

        printf("%d\n",ans);

    }

    return ;

}

今天的讲解就到这了，若果有没有听懂的可以借鉴一下《啊哈！算法》

巴特西

图论问题(2) : hdu 1102

最新文章

热门文章