1001 Battle Over Cities - Hard Version.c

#include
#include
#define inf 9999999

typedef struct
{
    int city1city2coststatus;
}*HighwayHNode;

Highway H;

int nm*f*costmaxcost;

int cmp（const void *aconst void *b）
{
    Highway A=（Highway）a; Highway B=（Highway）b;
    if（A->status!=B->status）
        return B->status-A->status;
    else
        return A->cost-B->cost;
}

void initial（）
{
    int i;
    for（i=1;i<=n;i++）
        f[i]=i;
}

int findfather（int x）
{
    if（f[x]==x）
        return x;
    else return f[x]=findfather（f[x]）;
}

void Union（int xint y）
{
    int fx=findfather（x）;
    int fy=findfather（y）;
    if（fx==fy）
        return ;
    f[fx]=fy;
}

int main（）
{
    scanf（“%d%d“&n&m）;
    f=malloc（sizeof（int）*（n+1））;
    cost=malloc（sizeof（int）*（n+1））;
    H=malloc（sizeof（HNode）*m）;

    int i;
    for（i=1;i<=n;i++）
        {f[i]=i;cost[i]=0;}
    for（i=0;i        scanf（“%d%d%d%d“&H[i].city1&H[i].city2&H[i].cost&H[i].status）;

    qsort（Hmsizeof（HNode）cmp）;

    int jk;
    //printf（“1\n“）;
    for（i=1maxcost=0;i<=n;i++） //if city_i is conquered