首页 > 代码库 > 题目1417:变型金刚

题目1417:变型金刚

题目描述:

看过变形金刚的人一定记得这样一个场景,机器人在攻击人类的时候,可以上天入地,并且都如履平地。

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

输入:

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

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

输出:

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

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

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




--------------------------------------------------------------------------------------------------------------------------

思想:因为输入的是字符串,所以应该把字符串与Tree数组下标结合起来,所以使用map恰到好处。把基地的“名称”从字符串装换为整型变得好处理后,问题就很常规了。


Code:
#include <iostream>#include <algorithm>#include <map> using namespace std; struct Station{    string base1;    string base2;    int int_base1;    int int_base2;    int cost;}; map<string,int> baseTransfer;Station base[10010];int Tree[110]; void initTree(int length){    for(int i=0;i<=length;++i)        Tree[i]=-1;} int find_Root(int x){    if(Tree[x]==-1)        return x;    else{        int tmp=find_Root(Tree[x]);        Tree[x]=tmp;        return tmp;    }} bool cmp(Station a,Station b){    return a.cost<=b.cost;} int main(){   int n,m,index;   while(cin>>n>>m){        baseTransfer.clear();        index=1;        for(int i=0;i<m;++i){            cin>>base[i].base1>>base[i].base2>>base[i].cost;            if(baseTransfer.find(base[i].base1)==baseTransfer.end())                baseTransfer.insert(make_pair(base[i].base1,index++));            if(baseTransfer.find(base[i].base2)==baseTransfer.end())                baseTransfer.insert(make_pair(base[i].base2,index++));        }        for(int i=0;i<m;++i){            base[i].int_base1=baseTransfer[base[i].base1];            base[i].int_base2=baseTransfer[base[i].base2];        }        if(baseTransfer.size()<(unsigned int)n){            cout<<"My God"<<endl;            continue;        }        initTree(n);        sort(base,base+m,cmp);        int maxlength=0;        for(int i=0;i<m;++i){            int root_a=find_Root(base[i].int_base1);            int root_b=find_Root(base[i].int_base2);            if(root_a!=root_b){                Tree[root_a]=root_b;                if(base[i].cost>maxlength)                    maxlength=base[i].cost;            }        }        int cnt=0;        for(int i=1;i<=n;++i)            if(Tree[i]==-1)                ++cnt;        if(cnt==1)            cout<<maxlength<<endl;        else            cout<<"My God"<<endl;   }   return 0;} /**************************************************************    Problem: 1417    User: lcyvino    Language: C++    Result: Accepted    Time:330 ms    Memory:3832 kb****************************************************************/

 



 

题目1417:变型金刚