Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:test data

Posted by swust20105376 at 2012-07-14 13:41:58 on Problem 2337
In Reply To:Re:test data Posted by:swust20105376 at 2012-07-14 13:37:59
>  这上面的我都过了,为什么还RE???
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<cstdlib>
using namespace std;

const int N=30;
const int Max=10010;

struct node
{
	int to,id;
};

vector<node>v[N];
stack<int>sta;
int fa[N],n;
bool u[Max];
string s[Max];

int find(int x)
{
	if(fa[x]!=x)return fa[x]=find(fa[x]);
	return fa[x];
}

bool dfs(int x,int cnt)
{
	int i;
	if(cnt==n)return true;
	for(i=0;i<v[x].size();i++)
	{	
		node t=v[x][i];  
		if(u[t.id]==0)
		{
			u[t.id]=1;
			if(dfs(t.to,cnt+1))
			{
				sta.push(t.id);
				return true;
			}
			u[t.id]=0;
		}
	}
	return false;
}

void get_ans()
{
	int t=sta.top();
	sta.pop();                  //printf("%d ",t);
	cout<<s[t];
	while(!sta.empty())
	{
		t=sta.top();           //printf("%d ",t);
		sta.pop();
		cout<<"."<<s[t];
	}
	printf("\n");
//	for(int i=0;i<n;i++)printf("%s ",s[i]);
	return;
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int i,j,ok[N]={0},out[N]={0},in[N]={0};
		scanf("%d",&n);
		getchar();
		memset(s,0,sizeof(s));
		for(i=0;i<26;i++)
		{
			fa[i]=i;
			v[i].clear();
		}
		for(i=0;i<n;i++)cin>>s[i];
		sort(s,s+n);
		for(i=0,j=0;i<n;i++)
		{
			int x=s[i][0]-'a',y=s[i][s[i].size()-1]-'a';
			node t={y,j};
			v[x].push_back(t);
			j+=1;
			out[x]+=1,in[y]+=1;
			ok[x]=ok[y]=1;
			x=find(x),y=find(y);
			if(x!=y)fa[y]=x;
		}
		int cnt=0,num=0,flag=0,a[10];
		for(i=0;i<26;i++)
		{
			if(ok[i])
			{
				if(in[i]!=out[i])a[num++]=i;
				if(fa[i]==i)cnt+=1;
				if(cnt>1||num>2)
				{
					flag=1;
					break;
				}
			}
		}
		for(i=0;i<n;i++)cout<<s[i]<<" ";
		printf("\n");
		if(flag)printf("***\n");
		else
		{
			memset(u,0,sizeof(u));
			if(num==0)
			{
				for(i=0;i<26;i++)
				{
					if(ok[i]&&dfs(i,0))get_ans();
				}
				
			}
			else if(num==2)
			{	
				if(out[a[0]]-in[a[0]]==1&&in[a[1]]-out[a[1]]==1&&dfs(a[0],0))get_ans();
				else if(out[a[1]]-in[a[1]]==1&&in[a[0]]-out[a[0]]==1&&dfs(a[1],0))get_ans();
				else printf("***\n");
				//for(i=0;i<v['t'-'a'].size();i++)printf("%d ",v['t'-'a'][i].to);
			}
			else printf("***\n");
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator