Ice_cream’s world III

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3045    Accepted Submission(s): 1070

Problem Description

ice_cream’s world becomes stronger and stronger; every road is built as undirected. The queen enjoys traveling around her world; the queen’s requirement is like II problem, beautifies the roads, by which there are some ways from every city to the capital. The project’s cost should be as less as better.

Input

Every case have two integers N and M (N<=1000, M<=10000) meaning N cities and M roads, the cities numbered 0…N-1, following N lines, each line contain three integers S, T and C, meaning S connected with T have a road will cost C.

Output

If Wiskey can’t satisfy the queen’s requirement, you must be output “impossible”, otherwise, print the minimum cost in this project. After every case print one blank.

Sample Input

2 1
0 1 10

4 0

Sample Output

10

impossible

Ice_cream世界第三

问题描述

冰淇淋的世界变得越来越强大;每条路都是没有方向的。女王喜欢周游世界;女王的要求就像第二个问题，美化了道路，每个城市都有一些通往首都的路。这项工程的成本应该既少又好。

输入

N-1，下面有N条线，每条线包含三个整数S, T和C，意思是S连接到T有一条道路将花费C。

输出

如果Wiskey不能满足皇后的要求，你必须输出“不可能”，否则，打印这个项目的最低成本。在每个案例之后打印一个空白。

Sample Input

2 1
0 1 10

4 0

Sample Output

10

impossible

题目大意很简单

就是给你城市的数量，和可以修建的铁路及其长度，如果连通，输出最小的总长，否则输出impossible

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include<algorithm>
using namespace std;
#define N 1010
#define LL long long
int n,M,S,T,C,t,k;
LL ans;
int fa[N];
struct Path
{
    int x,y,d;
    bool operator<(const Path &m)const
    {
        return d<m.d;
    }
}path[10010];

int getHead(int x)
{
    int a=x;
    while(x!=fa[x])
	x=fa[x];
    fa[a]=x;
    return x;
}

bool Union(int x,int y)
{
    int fa_x=getHead(x);
    int fa_y=getHead(y);
    if(fa_x==fa_y)
	return false;
    fa[fa_x]=fa_y;
    return true;
}

int main()
{
    while(scanf("%d%d",&n,&M)!=EOF)
	{
        t=0,k=0,ans=0;
        for(int i=0;i<n;i++)
	    fa[i]=i;
        if(n==0)
	{
	    cout<<0<<endl;
	    continue;
	}
        for(int i=0;i<M;i++)
	    scanf("%d%d%d",&S,&T,&C),path[k].x=S,path[k].y=T,path[k++].d=C;
        sort(path,path+k);
        for(int i=0;i<k;i++)
	{
            if(Union(path[i].x,path[i].y))
                ans+=path[i].d,t++;
        }
        if(t==n-1)
	    cout<<ans<<endl;
        else
	    cout<<"impossible"<<endl;
        cout<<endl;
    }
    return 0;
}