首页 > 代码库 > HDU 1181 并查集 or SPFA

HDU 1181 并查集 or SPFA

2024-07-11 00:30:08   234人阅读

变形课

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 12773    Accepted Submission(s): 4733


Problem Description
呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体. 
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.
 
Input
测试数据有多组。每组有多行，每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.
 
Output
如果Harry可以完成他的作业,就输出"Yes.",否则就输出"No."(不要忽略了句号)
 
Sample Input
so
soon
river
goes
them
got
moon
begin
big
0
 
Sample Output
Yes.
 
Hint
Hint
Harry 可以念这个咒语:"big-got-them".
 
 
就像成语接龙一样，每个单词的首字符和前面单词的尾字符相等，只要使得首单词的首字符为‘b’且尾单词的尾字符为‘m‘就输出yes.   若不能构成这个结构输出no.
 
那么就有两种方法，SPFA或者并查集。
 
SPFA算法使dis[‘m‘-‘a‘]！=inf即从‘m‘-‘a‘到‘b‘-‘a‘之间有一条路径则满足条件输出yes。
 
SPFA代码：
 1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <vector> 5 #include <queue> 6 #define inf 999999999 7 using namespace std; 8  9 10 int map[27][27];11 int dis[27];12 int visited[27];13 14 15 void init()16 {17     for(int i=0;i<27;i++)18     {19         visited[i]=0;20         dis[i]=inf;21         for(int j=0;j<27;j++)22         map[i][j]=inf;23     }24 }25 26 27 void SPFA()28 {29     queue<int>Q;30     int u, v;31     Q.push(1);32     visited[1]=1;33     dis[1]=0;34     while(!Q.empty())35     {36         u=Q.front();37         Q.pop();38         visited[u]=0;39         for(v=0;v<26;v++)40         {41             if(map[u][v]!=inf&&dis[v]>dis[u]+map[u][v])42             {43                 dis[v]=dis[u]+map[u][v];44                 if(!visited[v])45                 {46                     Q.push(v);47                     visited[v]=1;48                 }49             }50         }51     }52 }53 main()54 {55     char a[1001];56     while(scanf("%s",a)!=EOF)57     {58         init();59         int n=strlen(a);60         map[a[0]-‘a‘][a[n-1]-‘a‘]=1;61         while(scanf("%s",a))62         {63             if(strcmp(a,"0")==0) break;64             int n=strlen(a);65             map[a[0]-‘a‘][a[n-1]-‘a‘]=1;66         }67         SPFA();68         if(dis[‘m‘-‘a‘]!=inf)69         printf("Yes.\n");70         else printf("No.\n");71     }72 }

 

 

用并查集就是始终保持‘b‘-‘a‘为根结点，其他点为儿子，若father[‘b‘-‘a‘]==findroot(‘m‘-‘a‘)则满足条件。

并查集代码：

 1 #include <iostream>   2 #include <string>   3 using namespace std;   4 string str;   5 int father[30];   6 int find(int x)   7 {   8     if(x!=father[x])   9         father[x]=find(father[x]);  10     return father[x];  11 }  12 void mere(int x,int y)  13 {  14     x=find(x);  15     y=find(y);  16     if(x!=y)  17         father[y]=x;  18 }  19 int main()  20 {  21     int i;  22     while(cin>>str)  23     {  24         memset(father,0,sizeof(father));  25         for(i=0;i<29;i++)  26             father[i]=i;  27         int len=str.length();  28         int x=find(str[0]-‘a‘);  29         int y=find(str[len-1]-‘a‘);  30         if(x!=y&&y!=‘b‘-‘a‘)  31             mere(x,y);  32         while(cin>>str)  33         {  34             if(!str.compare("0"))  35                 break;  36             len=str.length();  37             x=find(str[0]-‘a‘);  38             y=find(str[len-1]-‘a‘);  39             if(x!=y&&y!=‘b‘-‘a‘)  40                 mere(x,y);  41         }  42         x=find(‘m‘-‘a‘);  43         y=father[‘b‘-‘a‘];  44         if(x!=y)  45             cout<<"No."<<endl;  46         else  47             cout<<"Yes."<<endl;  48     }  49     return 0;  50 }

 


联系
我们