POJ 3723 Conscription

[PRIM]

存圖好麻煩= =

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
#define R 50000
#define N 20020
#define INF -1
using namespace std;
class Edge
{
public:
    int a,b,w;
    Edge():a(0),b(0),w(0){}
    void Print()const

    {
        printf("%d------%d   %d\n",a,b,w);
    }
};

int Girl,Boy,egcnt=0;
Edge Edges[2*R+2*N];
int Startptr[N];
int Endptr[N];
bool IsVis[N];
priority_queue<Edge, deque<Edge>, greater<Edge> > BFS;
void Connect(int Gind,int Bind,int w)
{
    Edges[egcnt].a=Bind;
    Edges[egcnt].b=Gind;
    Edges[egcnt].w=10000-w;
    egcnt++;
    Edges[egcnt].a=Gind;
    Edges[egcnt].b=Bind;
    Edges[egcnt].w=10000-w;
    egcnt++;
}
void Reprc()
{
    sort(Edges,Edges+egcnt);
    for(int lx=0;lx<=Boy+Girl;lx++)
        Startptr[lx]=-1,Endptr[lx]=-1;
    for(int lx=0;lx<egcnt;lx++)
    {
        if(Startptr[Edges[lx].a]==-1)
            Startptr[Edges[lx].a]=lx;
        Endptr[Edges[lx].a]=lx;
    }
}
void Add(int I)
{
    IsVis[I]=true;
    if(Startptr[I]==-1) return;
    for(int lx=Startptr[I];lx<=Endptr[I];lx++)
        if(IsVis[Edges[lx].b]==false)
            BFS.push(Edges[lx]);
    return;
}
void Clear()
{
    memset(IsVis,false,sizeof(IsVis));
    egcnt=0;
    while(BFS.size())
        BFS.pop();
}
bool operator<(Edge a1,Edge a2)
{
    if(a1.a<a2.a)
        return true;
    else if(a1.a==a2.a)
        return (a1.b<a2.b);
    return false;
}
bool operator>(Edge a1,Edge a2)
{
    return (a1.w>a2.w);
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        Clear();
        int _ES;
        scanf("%d %d %d",&Girl,&Boy,&_ES);
        for(int lx=1;lx<=Girl+Boy;lx++)
            Connect(0,lx,0);
        while(_ES--)
        {
            int x,y,w;scanf("%d %d %d",&x,&y,&w);
            Connect(x+1,y+Girl+1,w);
        }
        Reprc();
        Add(0);
        long long int Cost=0;
        while(BFS.size())
        {
            Edge pp=BFS.top();
            BFS.pop();
            if(IsVis[pp.b]) continue;
            Cost+=(long long int)pp.w;
            Add(pp.b);
        }
        printf("%I64d\n",Cost);
    }
    return 0;
}