《计算机算法设计与分析》电子工业出版社·第4版 算法实现题 6-2

i6-2.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ML 1024
typedef struct node {
    int n;          // current edge (has put into)
    int w;          // current weight.
    int flag[ML];   // whether V[i] is used.
    struct node *next;
} Node;

Node* Node_new(int n, int w, int flag[]) {
    Node *p = (Node*) malloc(sizeof(Node));
    if (p == NULL)
        return NULL;
    int i;
    p->n = n;
    p->w = w;
    p->next = NULL;
    for (i = 0; i < ML; i++) {
        p->flag[i] = flag[i];
    }
    return p;
}

void Node_prepend(Node **list, Node *node) {
    node->next = *list;
    *list = node;
}

Node* Node_pop_min(Node **list) {
    if (*list == NULL) {
        return NULL;
    }
    Node *min = *list;
    Node *p;
    for (p = (*list)->next; p != NULL; p = p->next) {
        if (p->w < min->w) {
            min = p;
        }
    }
    if (min == *list) {
        *list = min->next;
    } else {
        for (p = *list; p->next != min; p = p->next);
        p->next = p->next->next;
    }
    return min;
}

int main(const int argc, const char **argv) {
    int nV, nE;     // n = nV number of Vertex, m = nE number of Edge.
    int V[ML], E[ML][2];
    int i;

    scanf("%d %d", &nV, &nE);
    if (nV > ML || nE > ML) {
        printf("Overflow! Max size is %d.\n", ML);
        return 1;
    }
    for (i = 0; i < nV; i++) {
        scanf("%d", &V[i]);
    }
    for (i = 0; i < nE; i++) {
        scanf("%d %d", &E[i][0], &E[i][1]);
        E[i][0]--;
        E[i][1]--;
    }

    int flag0[ML];
    memset(flag0, 0, sizeof(flag0));
    Node *list = Node_new(-1, 0, flag0);
    int e;              // Current edge
    Node *p, *q;        // Current node, Child node
    while (list != NULL) {
        p = Node_pop_min(&list);
        e = p->n + 1;
        if (e > nE) {
            break;
        }
        for (i = 0; i < 2; i++) {
            q = Node_new(e, p->w, p->flag);
            if (p->flag[ E[e][i] ] == 0) {
                q->w += V[ E[e][i] ];
                q->flag[ E[e][i] ] = 1;
            }
            Node_prepend(&list, q);
        }
        free(p);
    }

    printf("%d\n", p->w);
    for (i = 0; i < nV; i++) {
        printf("%d ", p->flag[i]);
    }
    printf("\n");

    return 0;
}