zoj 1372, minimal spanning tree, prim algorithm - 行者无疆 始于足下 - 行走,思考,在路上

zoj 1372, minimal spanning tree, prim algorithm

xiaohanyu posted @ Thu, 27 May 2010 00:32:22 +0800 in Algorithm with tags ZOJ Algorithm , 1942 readers

在实验室睡了一宿。昨儿一激动改了/etc/make.conf:

ACCEPT_KEYWORDS="~x86"

主要是想体验一下传说中的gnome 2.30和gnome shell,探索半天才知道我原来的gentoo用的是stable version,这样一改就改成“以后要用testing version"。

sudo emerge -avuND world

这下好了,乖乖,总共有573个软件包要更新,需要下载1.7G的东西。天知道这1.7G的代码在我的本本上要编译多长时间。不过,量小非君子,无毒不丈夫,索性心一横,就输了yes,让本本自己在那边呼啸去了。

编译到170左右个包时出现了麻烦,libmtp无法编译,我一看是因为其依赖的libpng是1.2版本的,而gentoo testing version的libpng是1.4版本的,这样来来回回搞了许久,终于在google上找到了这篇文章,暂且解决了这个问题。

折腾期间又扫了一眼emerge man page,了解了几个有用的参数如:

  • --skip-first
  • --keep-going
  • --resume

中途还有几个blocked的包,解决方法大概是先uninstall再reinstall,一般就行了;再不行看看USE参数,略微改一下,总之,元发行版,麻烦与灵活共存。

编译的过程emacs死掉了,于是再也无法打开^~~^……就这能干看一些题目。zoj 1372,第一眼一看就是图论的题目。反正也是闲着,临阵磨枪,找来了算法导论,补补图论的基础知识。进一步了解了BFS和DFS,看懂了最小生成树的Prim算法,并参照着别人的代码,采用邻接矩阵的方式,还AC了。真实不容易啊。不过收获也是大大的。

代码: 

#include <iostream>
#include <string>
using namespace std;

const long max_points = 100;
const long infinity = 1000001;

int p, r, length, g[max_points][max_points];
bool flag;

class vertex
{
public:
    int distance;
    bool visited;
};

vertex v[max_points];

void initial()
{
    for(int i = 1; i <= p; i++)
        for(int j = 1; j <= p; j++)
            g[i][j] = infinity;
}

void prim(int origin)
{
    int temp_min;
    int temp_v = 0;
    int sum = 0;

    for(int i = 1; i <= p; i++)
    {
        v[i].distance = g[i][origin];
        v[i].visited = false;
    }

    v[origin].distance = 0;
    v[origin].visited = true;

    sum++;

    while (sum < p)
    {
        temp_min = infinity;
        for(int i = 1; i <= p; i++)
            if(v[i].visited == false && v[i].distance < temp_min)
            {
                temp_min = v[i].distance;
                temp_v = i;
            }
        
        if(temp_min < infinity)
        {
            length += v[temp_v].distance;
            v[temp_v].visited = true;
            sum++;
        }
        else
        {
            flag = true;
            break;
        }

        for(int i = 1; i <= p; i++)
        {
            if(v[i].visited == false && v[i].distance > g[i][temp_v])
            {
                v[i].distance = g[i][temp_v];
            }
        }
    }
}

int main(int argc, char *argv[])
{
    int a, b, c;

    while(cin >> p)
    {
        if(p == 0)
            break;
        cin >> r;

        initial();

        for(int i = 0; i < r; i++)
        {
            cin >> a >> b >> c;
            if(c < g[a][b])
                g[a][b] = g[b][a] = c;
        }
        length = 0;
        prim(1);

        cout << length << endl;
    }

    return 0;
} 

Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee