zw_xmuleea-11168271-1001BattleOverCities-HardVersion.zip

zw_xmuleea-11168271-1001BattleOverCities-HardVersion.zip

#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
    {
        initial（）;
        for（j=0;j        {
            if（H[j].city1==i||H[j].city2==i）
                continue;
            if（H[j].status==1）
                Union（H[j].city1H[j].city2）;
            else
            {
                    if（findfather（H[j].city1）!=findfather（H[j].city2））
                    {
                        Union（H[j].city1H[j].city2）;
                        cost[i]+=H[j].cost;
                    }

            }
        }
        for（j=1;j<=n;j++）
        {
            if（j==i）
                continue;
            for（k=1;k<=n;k++）
            {
                if（k!=i）
                {
                    if（findfather（j）!=findfather（k））
                    {cost[i]=inf;break;}
                }
            }
            break;
        }
        if（cost[i]>maxcost）
            maxcost=cost[i];
    }

    int flg=0;
    if（maxcost==0）
        printf（“0“）;
    else
        for（i=1;i<=n;i++）
            if（cost[i]==maxcost）
                if（flg==0） {printf（“%d“i）;flg=1;}
                else printf（“ %d“i）;
    return 0;

}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        2285  2019-07-21 15:17  \xmuleea-11168271-1001 Battle Over Cities - Hard Version.c
     文件          36  2019-07-21 15:17  \no.txt