Blog·Tanky WooABOUTRSS

HDOJ 1875 畅通工程再续

16 Sep 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
资料
最小生成树(MST)讲解请看: [http://www.wutianqi.com/?p=1284](http://www.wutianqi.com/?p=1284)

题目传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1875 Prim版本: 31MS 372K 1314 B C++ 解答报告:

#include 
#include 
using namespace std;
const int INF = 10000000;

double arcs[205][205], dis[205];
int x[205], y[205], vis[205];
int nCases, islands;
int x_tmp, y_tmp, rec;
double tmp, _min;
bool flag;
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &nCases;);

    while(nCases--)
    {
        scanf("%d", &islands;);
        for(int i=0; i1000)
                    tmp = INF;
                arcs[i][j] = arcs[j][i] = tmp;
            }
        }
        for(int i=1; i

Kruskal版本: 187MS 284K 1654 B C++ 解答报告:

#include 
#include 
#include 
using namespace std;
typedef struct Road
{
    int c1, c2;
    double cost;
}Road;

struct Point
{
    int x, y;
};

bool myCompare(const Road &a;, const Road &b;)
{
    if(a.cost < b.cost)
        return 1;
    return 0;
}

Road road[5051];
Point point[101];
int city[101];

int Find(int n)
{
    if(city[n] == -1)
        return n;
    return city[n] = Find(city[n]);
}

bool Merge(int s1, int s2)
{
    int r1 = Find(s1);
    int r2 = Find(s2);
    if(r1 == r2)
        return 0;
    if(r1 < r2)
        city[r2] = r1;
    else
        city[r1] = r2;
    return 1;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int n;
    int nCases;
    scanf("%d", &nCases;);
    while(nCases--)
    {
        scanf("%d", &n;);
        for(int i=0; i=10 && Merge(road[i].c1, road[i].c2))// ??????
            {
                count ++;
                sum += road[i].cost;
            }
            if(count == n-1)
                break;
        }
        if(count == n-1)
            printf("%.1lf\n", sum*100);
        else
            puts("oh!");
    }
    return 0;
}