HDU 4966 GGS-DDU

直接膜拜DJWS的最小樹形圖@@

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef struct _link{int a, b, w;}link;
link links[10000]; int E;
void add_link(int a, int b, int w = 0){
    link nl;
    nl.a = a, nl.b = b, nl.w = w;
    links[E] = nl;
    E++;
    return;
}
int _cnt = 0; int new_vertex(){ _cnt++; return _cnt-1; }
int cal_mst(int root){
    int wei[600], src[600], vis[600], tenta[600], cons[600];
    int w1 = 0, w2 = 0;
    const int INF_weight = 10000;
    memset(cons, 0, sizeof(cons));
    /*for(int lx = 0;lx < E;lx++){
        printf("%d -> %d w=%d\n", links[lx].a, links[lx].b, links[lx].w);
    }*/
    int V = _cnt;
    for(;;){
        //printf("E = %d\n", E);
        memset(wei, 1, sizeof(wei));
        memset(src, -1, sizeof(src));

        for(int lx = 0;lx < E;lx++){
            int& a = links[lx].a;
            int& b = links[lx].b;
            int& w = links[lx].w;
            if(a != b and b != root and w < wei[b])
                wei[b] = w, src[b] = a;
        }
        /*for(int  lx = 0;lx < _cnt;lx++){
            printf("get %d <- %d w=%d\n", lx, src[lx], wei[lx]);
        }*/
        // Jellyfish
        memset(vis, -1, sizeof(vis));
        memset(tenta, -1, sizeof(tenta));

        w1 = 0;
        bool jizzy = false;
        for(int lx =  0;lx < V;lx++){
            if(cons[lx]) continue;
            if(src[lx] == -1 and lx != root) return -1;
            if(src[lx] >= 0) w1 += wei[lx];
            //printf("do at %d\n", lx);
            int s = lx;
            for(;s != -1 and vis[s] == -1;s = src[s]){
                //printf("vis at %d\n", s);
                vis[s] = lx;
            }

            if(s != -1 and vis[s] == lx){
                jizzy = true;
                int j = s;//printf("found s = %d\n", s);
                do{
                    tenta[j] = s; cons[j] = 1;
                    w2 += wei[j]; j = src[j];
                    //printf("j = %d\n", j);
                }while(j != s);
                cons[s] = 0;
            }
        }
        if(jizzy == false) break;
        for(int ly = 0;ly < E;ly++){
            int& a = links[ly].a;
            int& b = links[ly].b;
            int& w = links[ly].w;
            if(tenta[b] >= 0) w -= wei[b];
            if(tenta[a] >= 0) a = tenta[a];
            if(tenta[b] >= 0) b = tenta[b];
            if(a == b) links[ly--] = links[--E];
        }
    }
    return w1+w2;
}
int main()
{
    int an[55];
    int anode[55][551];
    int n, m;while(1){

        scanf("%d %d", &n, &m);
        if(n == 0  and m == 0 ) break;

        _cnt = 0;
        E = 0;

        for(int lx = 0;lx < n;lx++)
            scanf("%d", an+lx);

        int root = new_vertex();
        for(int lx = 0;lx < n;lx++)
            for(int ly = 0;ly <= an[lx];ly++)
                anode[lx][ly] = (new_vertex());

        for(int lx = 0;lx < n;lx++){
            add_link(root, anode[lx][0]);
            for(int ly = 1;ly <= an[lx];ly++)
                add_link(anode[lx][ly], anode[lx][ly-1]);
        }

        while(m--){
            int c1, l1, c2, l2, money;
            scanf("%d %d %d %d %d", &c1, &l1, &c2, &l2, &money);
            add_link(anode[c1-1][l1], anode[c2-1][l2], money);
        }
        //------build graph ok
        printf("%d\n", cal_mst(root));
    }
    return 0;
}