首页 > ACM题库 > HDU-杭电 > hdu 2122 Ice_cream’s world III-最小生成树-[解题报告]C++
2013
12-29

hdu 2122 Ice_cream’s world III-最小生成树-[解题报告]C++

Ice_cream’s world III

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

2 1
0 1 10

4 0

样例输出:

10

impossible

AC代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAX 0x3f3f3f3f
int weight[1001][1001];

int main(){
    
    int lowcost[1001];
    int N, M, ans;
	int flag = 0;

    while( scanf( "%d%d", &N, &M ) != EOF ){
        memset( weight, 0x3f, sizeof( weight ) );
        
        for( int i = 0; i < M; i++ ){
            int temp1, temp2, temp3;
            cin >> temp1 >> temp2 >> temp3;
            if( weight[temp1][temp2] > temp3 ){
                weight[temp1][temp2] = temp3;
                weight[temp2][temp1] = temp3;
            }
        }
        
        for( int i = 1; i < N; i++ ){
            lowcost[i] = weight[i][0];
        }
        lowcost[0] = -1;

        int ans = 0;
        for( int i = 1; i < N; i++ ){
            int mindis = MAX;
            int k = 1;
            for( int j = 1; j < N; j++ ){
                if( lowcost[j] < mindis && lowcost[j] != -1 ){
                    mindis = lowcost[j];
                    k = j;
                }
            }
            if( mindis == MAX ){
                ans = MAX;
                break;
            }
            ans += mindis;
			lowcost[k] = -1;
            for( int j = 1; j < N; j++ ){
                if( weight[k][j] < lowcost[j] ){
                    lowcost[j] = weight[k][j];
                }
            }
        }

        if( ans == MAX ){
            cout << "impossible" << endl;
        }else{
            cout << ans << endl;
        }
		cout << endl;
    }
    return 0;
}

 

解题转自:http://blog.csdn.net/hzh_0000/article/details/14526307


  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  3. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  4. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。