何时“苏醒”? Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB Total submit users: 61, Accepted users: 41 Problem 10843 : No special judgement Problem description 人类的大脑是按功能分区的。正常人的大脑分区都是活跃的，分区之间有着广泛的神经连接；而脑病患者的某些大脑分区则是不活跃的，处于“睡眠”状态。最近的研究发现：如果某个“睡眠”分区X与其它至少3个活跃分区保持连接1年时间，则分区X会“苏醒”过来，恢复成活跃状态。 “苏醒”后的分区不会再转入“睡眠”状态。 有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后，其中3个分区同时“苏醒”过来。根据上文的结论，若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来？ Input 输入文件的第1行仅包含1个整数M，取值范围是[3, 26]，它表示病人大脑的分区数。第2行也只包含1个非负整数N，它表示分区之间的连接数（如果分区A与分区B相连，则分区B也与分区A相连。由于这样的连接是等价的，所以只计数1次）。第3行包含3个相邻的大写英文字母，分别代表刚刚同时“苏醒”的3个分区。第4行中包含N个用空格分割的字符串，每个字符串包含2个大写英文字母，分别代表2个相连接的分区。 Output 如果该病人的大脑分区经过若干年后能够全部“苏醒”，请在输出文件中按格式输出一行：“WAKE UP IN n YEARS” （其中n指分区全部“苏醒”需要的年数）如果该病人的大脑分区无法全部“苏醒”，请在输出文件中按格式输出一行：“THIS BRAIN NEVER WAKES UP” Sample Input 6 11 HAB AB AC AH BD BC BF CD CF CH DF FH Sample Output WAKE UP IN 3 YEARS Problem Source 湖南省第二届程序设计大赛/// 这个题比较简单，只要设一个二维数组表示分区的连接情况/// 用一维数组记录已经苏醒的分区 #include <iostream>#include <vector>using namespace std;int main() {     int  n;    while(cin>>n){        char buf[4];        int m,y,i,j,w,t;        bool status[26] = {false},a[26][26] = {false};        cin>>m;        cin>>buf;        status[buf[2]-'A']=status[buf[1]-'A']=status[buf[0]-'A']=true;        for(i=0; i<m; i++){            cin>>buf;            a[buf[0]-'A'][buf[1]-'A']=a[buf[1]-'A'][buf[0]-'A']=true;        }        bool flag=true;        vector<int> wake;        for(w=3,y=0; flag && w<m; y++){            wake.clear();            for(i=0; i<26; i++){                if(status[i])                    continue;                for(t=j=0; j<26; j++){                    if(a[i][j] && status[j])                        t++;                    if(t>=3)                        break;                }                if(j<26)                    wake.push_back(i);            }            if(wake.empty())                break;            for(i=0; i<wake.size(); i++){                w++;                status[wake[i]]=true;            }        }        if(w==n)            cout<<"WAKE UP IN "<<y<<" YEARS"<<endl;        else            cout<<"THIS BRAIN NEVER WAKES UP"<<endl;    }    return 0; }  

评论