TIOJ 1445 機器人組裝大賽 [次小生成樹]

poao899    13860K    1730MS    G++     1.90K     2010-03-24 19:14:56                                        .


次小生成樹。

利 用k小生成樹定理

變成 V^2(有點類似RMQ的東東) + E*O(1)(查詢)


被               long long              表= =



//*********************************

#include<cstdio>
#include<algorithm>
#define MAXV 1010
#define MAXE 500000

long long mst,mst2;
int n,m;
//gn
int getint(){
    int g=0,c=getchar(),s=1;
    while(c==10||c==32||c==9)c=getchar();
    if(c=='-'){s=-1;c=getchar();}
    while(c>='0'&&c<='9'){
        g=g*10+c-48;
        c=getchar();
    }
    return g*s;
}
long long get64(){
    long long g=0;int c=getchar(),s=1;
    while(c==10||c==32||c==9)c=getchar();
    if(c=='-'){s=-1;c=getchar();}
    while(c>='0'&&c<='9'){
        g=g*10+c-48;
        c=getchar();
    }
    return g*s;
}
//kruskal's necessity
struct ways{
    int i,j;
    long long c;
    bool used;
    void get(){
        i=getint();j=getint();c=get64();
    }
    bool operator<(const ways &b)const{
        return c<b.c;
    }
}w[MAXE];
int root[MAXV];
int find(int a){
    return root[a]==a?a:root[a]=find(root[a]);
}
int uni(int a,int b){
    int ra=find(a),rb=find(b);
    root[ra]=rb;
}
//DFS' necessity
struct edge{
    int j;
    long long c;
    edge *next;
}e[MAXE],*v[MAXV];
void push(int i,int j,int c){
    static int cnt=0;
    edge *p=e+cnt++,*q;
    p->j=j;p->c=c;
    q=v[i];
    v[i]=p;
    p->next=q;
}
bool visited[MAXE],dfsed[MAXE];
long long dp[MAXV][MAXV];
int now;
void dfs(int n){
    edge *p=v[n];
    visited[n]=1;
    for(;p!=NULL;p=p->next)
        if(!visited[p->j]){
            dp[now][p->j]=dp[now][n]>p->c ? dp[now][n] : p->c;
            dfs(p->j);
        }
}
int main(){
    //input
    n=getint();m=getint();
    for(int i=0;i<m;i++)
        w[i].get();
    //kruskal
    std::sort(w,w+m);
    int edgeAdded=0;
    for(int i=0;i<=n;i++)root[i]=i;
    for(int i=0;i<m && edgeAdded<n-1;i++){
        if(find(w[i].i)!=find(w[i].j)){
            uni(w[i].i , w[i].j);
            edgeAdded++;
            mst+=w[i].c;
            //build gragh
            push(w[i].i,w[i].j,w[i].c);
            push(w[i].j,w[i].i,w[i].c);
            w[i].used=1;
        }
    }
        //if can't find MST
    if(edgeAdded!=n-1){puts("-1 -1");return 0;}
    printf("%I64d ",mst);
    //DFS, to find MST2
    mst2=9223372036854775807LL;
    for(int z=0;z<m;z++){
        if(w[z].used)continue;
        int x=w[z].i,y=w[z].j;
        if(dfsed[x])
            mst2=mst2<w[z].c-dp[x][y]?mst2:w[z].c-dp[x][y];
        else if(dfsed[y])
            mst2=mst2<w[z].c-dp[y][x]?mst2:w[z].c-dp[y][x];
        else{
            //init
            for(int i=0;i<MAXV;i++)
                visited[i]=0;
            now=x;dfsed[x]=1;
            dfs(x);
            mst2=mst2<w[z].c-dp[x][y]?mst2:w[z].c-dp[x][y];
        }
    }
    if(mst2==9223372036854775807LL)puts("-1");
    else printf("%I64d\n",mst+mst2);
}