デブンキー一家の大活躍

パソコン甲子園2008予選より
高校生がやるやつなのにね

ハイパー恥さらしタイム！はっじまっるよー！

プリム法で解を求めていたソースがあったので、こちらはクラスカル法で解いてみる事に
いかソース

001: #include
002: #include
003:
004: typedef struct {
005: 　　int father;
006: } NODE;
007:
008: typedef struct {
009: 　　int node1;
010: 　　int node2;
011: 　　int cost;
012: } ARC;
013:
014: NODE node[100];
015: ARC arc[5000];
016: int n, m;
017:
018: int read_data(void);
019: int kruskal(void);
020: int cmp(const void *a, const void *b);
021:
022: int main(void)
023: {
024: 　　while (read_data()) {
025: 　　　　qsort(arc, m, sizeof(ARC), cmp);
026: 　　　　printf("%d\n", kruskal());
027: 　　}
028:
029: 　　return 0;
030: }
031:
032: int read_data(void)
033: {
034: 　　int i;
035:
036: 　　scanf("%d %d", &n, &m);
037: 　　if (n == 0 && m == 0)
038: 　　　　return 0;
039:
040: 　　for (i = 0;i < m;i++)
041: 　　　　scanf("%d %d %d", &arc[i].node1, &arc[i].node2, &arc[i].cost);
042: 　　　　return 1;
043: 　　}
044:
045: int cmp(const void *a, const void *b)
046: {
047: 　　ARC arc1 = *(ARC*)a;
048: 　　ARC arc2 = *(ARC*)b;
049:
050: 　　return (arc1.cost - arc2.cost);
051: }
052:
053: int kruskal(void)
054: {
055: 　　int i, total_cost, u, v;
056:
057: 　　for (i = 0;i < n;i++)
058: 　　　　node[i].father = i;
059: 　　total_cost = 0;
060:
061: 　　for (i = 0;i < m;i++) {
062: 　　　　u = arc[i].node1;
063: 　　　　v = arc[i].node2;
064:
065: 　　　　while (u != node[u].father)
066: 　　　　　　u = node[u].father;
067: 　　　　　　while (v != node[v].father)
068: 　　　　　　v = node[v].father;
069: 　　　　　　if (u != v) {
070: 　　　　　　　　node[u].father = v;
071: 　　　　　　　　total_cost += arc[i].cost;
072: 　　　　　　}
073: 　　}
074:
075: 　　return total_cost;
076: }


まぁ、プリム法でやってた人は40行くらいだったけどねorz