spider.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
#define MAXV 2000
#define MAXINT 200000
 
static int maxlength;
static int totallength;
static int v1,v2;
 
struct edgenode{
    int y;
    int weight;
    struct edgenode *next;
};
 
struct graph{
    edgenode *edges[MAXV+1];
    int degree[MAXV+1];
    int nvertices;
    int nedges;
};
 
void initialize_graph(graph *g) {
    int i;
 
    g->nvertices = 0;
    g->nedges = 0;
 
    for(i=1; i<=MAXV; i++) g->degree[i] = 0;
    for(i=1; i<=MAXV; i++) g->edges[i] = 0;
}
 
void insert_edge(graph *g, int x, int y, int weight) {
    edgenode *p;
 
    p = (edgenode*)malloc(sizeof(edgenode));
 
    p->weight = weight;
    p->y = y;
    p->next = g->edges[x];
 
    g->edges[x] = p;
 
    g->degree[x]++;
 
    edgenode *q;
 
    q = (edgenode*)malloc(sizeof(edgenode));
 
    q->weight = weight;
    q->y = x;
    q->next = g->edges[y];
 
    g->edges[y] = q;
 
    g->degree[y]++; 
 
}
 
bool read_graph(graph *g) {
    int i;
    int m;
    int x, y;
    int weight;
 
 
    initialize_graph(g);
 
    if (scanf("%d %d", &(g->nvertices), &m)==EOF) return false;
 
    for(i = 1; i <= m; i++) {
        scanf("%d %d %d", &x, &y, &weight);
        if (maxlength<weight) {
            maxlength=weight;
            v1 = x;
            v2 = y;
        }
        insert_edge(g,x,y,weight);
    }
 
    return true;
}
 
bool prim(graph *g, int start, int uztamje) {
    int i;
    edgenode *p;
    bool intree[MAXV+1];
    int distance[MAXV+1];
    int v;
    int w;
    int weight;
    int dist;
 
    for(i=1; i <= g->nvertices; i++) {
        intree[i] = false;
        distance[i] = MAXINT;
        //parent[i] = -1;
    }
 
    /*intree[v1]=*/intree[uztamje]=true;
    //totallength
 
    distance[start] = 0;
    v = start;
 
    while(intree[v] == false) {
        intree[v] = true;
        p = g->edges[v];
        while(p != NULL) {
            w = p->y;
            weight = p->weight;
            if((distance[w] > weight) && (intree[w] == false)) {
                distance[w] = weight;
                //parent[w] = v;
                //maxlength = max(weight, maxlength);
                //printf("w: %d\n",weight);
                totallength += weight;
            }
            p = p->next;
        }
 
        v = 1;
        dist = MAXINT;
        for(i = 1; i <= g->nvertices; i++) {
            if((intree[i] == false) && (dist > distance[i])) {
                dist = distance[i];
                v = i;
            }
        }
 
    }
    for (int i=1; i<=g->nvertices; i++) {
        if (!intree[i]) return false;
    }
    return true;
}
 
 
 
int main()
{
 
    graph *g = (graph*)malloc(sizeof(graph));
 
    while (read_graph(g)) {
        //maxlength = -1;
        totallength = 0;
        if (!prim(g,v1, v2)) {
            printf("disconnected\n");
            continue;
        }
        //printf("%d %d\n", maxlength, totallength);
        int total = totallength;
        totallength = 0;
        prim(g,v2, v1);
        printf("%d\n", min(total,totallength)-maxlength);
 
    }
    return 0;
}