在实验室睡了一宿。昨儿一激动改了 /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;
}