注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1116  

2013-05-03 19:07:50|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1116
题意:
有n个字符串,问能不能将n个字符串连接起来,使得每一个字符串的首字母等于前一个字符串的尾字母,每个字符串必须连进去一次。
题解:
欧拉回路,把每个字符串看成一个一条边,一条从头到尾的有向边,首尾的两个字符看成图中的两个点,建立一个邻接矩阵。
然后求每个点的入度和出度,如果有一点入度为0,出度为1,一点入度为1,出度为0,剩余的点入度等于出度,则符合条件(或者是所有的点都是入度等于出度)。
在判断的时候可以计算每个点的入度-出度,看最后的结果中,是否出现一次1,一次-1,其余的都是0(或者是所有的结果都是0)。

/*
* test.cpp
*
* Created on: 2013-05-02
* Author: fudq
* hdu 1116
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 1010
int n,ru[30],chu[30],f[30];
char str[N];

void init()
{
for(int i=0;i<26;i++)
f[i]=i;
}

int Find(int a)
{
if(a != f[a])
f[a]=Find(f[a]);
return f[a];
}

void Merge(int x,int y)
{
int fx,fy;
fx=Find(x);
fy=Find(y);
if(fx != fy)
f[fx]=fy;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(ru,0,sizeof(ru));
memset(chu,0,sizeof(chu));
init();
for(int i=0;i<n;i++)
{
scanf("%s",str);
int len=(int)strlen(str);
int a=str[0]-'a';
int b=str[len-1]-'a';
chu[a]++;
ru[b]++;
Merge(a,b);
}
int res=0;
for(int i=0;i<26;i++)
if(i == f[i] && (chu[i] || ru[i]))
res++;
if(res > 1)
{
printf("The door cannot be opened.\n");
continue;
}

int n1=0,n2=0,n3=0;
for(int i=0;i<26;i++)
{
int t=ru[i]-chu[i];
if(t == 1)
n1++;
else if(t == 0)
n2++;
else if(t == -1)
n3++;
}
if((n1==1 && n3==1 && n2==24) || (n1==0 && n3==0 && n2==26) )
printf("Ordering is possible.\n");
else
printf("The door cannot be opened.\n");
}
return 0;
}



  评论这张
 
阅读(120)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018