首页 > ACM题库 > 九度OJ > 九度-1417-变型金刚[解题代码]
2013
12-13

九度-1417-变型金刚[解题代码]

题目描述:

        看过变形金刚的人一定记得这样一个场景,机器人在攻击人类的时候,可以上天入地,并且都如履平地。
        聪明的人类很快就想到,可不可以也利用地下的攻势来跟机器人进行周旋。很快,人类就在地下建立了几个基地。现在这些基地之间要进行合作,必须有一些基地之间是有通道的,这样无论是运输补给还是进行交流都会方便很多。在每两个基地之间都建立一个通道,这是一个好的方法,基地之间的交流会变得极其方便。但是,同时要考虑到修地下通道所花的人力、物力、以及时间。现在时间很紧迫,必须选择一些通道来进行修建。根据对地形的分析及研究,人类确定了一些适合修建的备选通道。相信聪明的你很快会想到,这些通道也不用全部都修建,只要修建一些通道,使得任意两个基地之间都互相可达就可以了。通道修好后,还有最后一项工作要做,就是在每条修好的通道之间都铺设一段铁轨,铁轨需要的费用与通道的长度相同。同时,跟现实中的铁路不同,地下的铁路每次只能买一批固定长度的钢轨,每条通道用一条钢轨,如果钢轨的长度大于通道的长度,剩下的丢弃即可。现在人类将确定的备选通道的数目,每条通道连接的两个基地名称,以及这条通道的长度告诉你。请问购买的这一批钢轨的长度最短要多长才能满足要求?

输入:

输入的第一行包括基地的个数n(1<=n<=100),以及备选通道的个数m(1<=m<=10000)。

 接下来的m行,每行代表一个备选通道,其中包括两个字符串base1及base2,代表两个基地的名称(字符串的长度1<=len<=100),以及一个整数w(1<=w<=10000000),代表这两个基地之间的距离。

输出:

        输出购买的这一批钢轨的长度最短需要的长度。如果题目中给出的备选通道,不论你怎么选择,都不能使任意两个基地之间可以互相可达,那么请输出 “My God” 即可。

样例输入:
5 8
a b 2
a c 3
b d 4
a d 2
b c 1
d e 3
a e 2
c e 5
5 5
a c 3
a d 2
d e 3
a e 2
c e 5
样例输出:
2
My God
提示:

1.由于修建方案的不同,数据中给出的两个基地之间的距离可能有多个,取最短的那个即可。


cpp 代码如下:
#include<stdio.h>
#include<string.h>
int ans;
int n,m,map[105][105],a,b,c,cur,i,j,tmin,min_i;
bool visit[105];
char name[105][105],s[105];
const int M=1000000000;
int prim(){
	memset(visit,0,sizeof(visit));
	int sum = 1;
	for(i=1; i<n; i++){
		tmin=M;
		min_i=-1;
		for(j=1; j<n; j++){
			if(!visit[j] && tmin > map[0][j]){
				tmin=map[0][j];
				min_i=j;
			}
		}
		visit[min_i]=true;
		if(min_i == -1){
			return sum;
		}else{
			sum++;
			if(tmin > ans) ans = tmin;
			for(j=1; j<n; j++){
				if(map[min_i][j] < map[0][j])
					map[0][j] = map[min_i][j];
			}
		}
	}
	return sum;
}
int getIndex(){
	for(i=0; i<cur; i++){
		if(strcmp(name[i],s) == 0){
			return i;
		}
	}
	return cur;
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
    	cur=0;
    	ans=-1;
        for(i=0; i<n; i++) for(j=0; j<n; j++) map[i][j]=M;
        while(m--){
        	scanf("%s",s);
        	int a = getIndex();
        	if(cur == a)
        		strcpy(name[cur++],s);
        	scanf("%s",s);
        	int b = getIndex();
        	if(cur == b)
        		strcpy(name[cur++],s);
        	scanf("%d", &c);
        	if(c < map[a][b])
        		map[a][b]=map[b][a]= c;
        }
        if(n == prim())
        	printf("%d\n",ans);
        else
        	printf("My God\n");
    }
    return 0;
}
/**************************************************************
	Problem: 1417
	User: coder
	Language: C++
	Result: Accepted
	Time:100 ms
	Memory:1076 kb
****************************************************************/


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。