what makes me amused joyful is I use emacs coding this algorithm..:)
although i am not proficient in it at all.
besides, today I installed aqumacs in place of the built-in emacs of Mac. thereby（thus） reviewed the bash command and the profile .bash_profile
------------------------------------------------
poj 1258 Agri-Net
Input
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.
Output
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.
------------------------------------------------------
it's a basic MST problem using Kruskac's algorithm. (since Prime algorithm is kinda like djstrak algorithm which is practiced yesterday :)).
both the data structure and the algorithm are quite simple.
the key of K algorithm is Union-find & union
the code is:
代码 edges.sort(cmp); for (list < edge > ::iterator it = edges.begin(); it != edges.end(); it ++ ){ // if find set int x = ( * it).from; int y = ( * it).to; while (vertices[x].parent != x){ x = vertices[x].parent; // climb up } while (vertices[y].parent != y){ y = vertices[y].parent; // climb up } if (x == y){ // reject continue ; } else { // put the edge into A A += ( * it).weight; // flip, now the x, y is the ROOT !!!!! if (vertices[x].size <= vertices[y].size){ vertices[x].parent = y; // x's parent is set to y vertices[y].size = vertices[x].size + vertices[y].size; } else { vertices[y].parent = x; // y's parent is set to x vertices[x].size = vertices[x].size + vertices[y].size; } } // else do nothing }
the caveat doesn't belong to the algorithm issue... at first, I can not pass poi until I change the input
. the instruction itself doesn't mention this input format :( and thank God I didn't change my original implementation of algorithm, or it would be quite a waste of time ....
---------------------------------------------