| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:测试数据In Reply To:测试数据 Posted by:qlyzpqz at 2009-11-07 22:54:20 这里给的样例我都能通过为什么提交还是WA呢?
这是我的代码:
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<set>
using namespace std;
bool emerge[26];
int step[26];
struct vec
{
int ins;
int id;
set<int> outs;
}graph[26];
void initial()
{
memset(emerge,0,sizeof(emerge));
for(int i=0;i<26;i++)
{ graph[i].ins=0;
graph[i].id=i;
graph[i].outs.clear();
step[i]=1;
}
}
class mySort
{
private:
char letters[1000000];
int chars;
int relations;
int SUM;
int line;
int state;
string answer;
int left;
int right;
public :
int input();
void compute();
void print();
int relationConfirmed();
void checkOut(int entrance);
int refreshStep(int entrance);
};
int mySort::input()
{
cin>>chars>>relations;
if(chars ==0 && relations==0)
return 0;
char c='<';
initial();
SUM=0;
state=2;
answer.resize(chars);
for(int i=0;i<relations;i++)
cin>>letters[SUM++]>>c>>letters[SUM++];
}
void mySort::compute()
{
for(line=0;line< SUM/2;line++)
{
left= letters[line*2]-'A';
right= letters[line*2+1]-'A';
graph[right].ins=1;
graph[left].outs.insert(right) ;
emerge[left]=true;
emerge[right]= true;
if(relationConfirmed())
break;
if(state==0)
{ int entrance=0;
for(int i=25;i>=0;i--)
if(emerge[i]==true && graph[i].ins==0)
{ entrance=i;
break;
}
checkOut(entrance);
break; }
}
}
void mySort::print()
{
switch(state)
{ case 0: cout<<"Sorted sequence determined after "<<line+1<<" relations: "<<answer<<'.'<<endl;
break;
case 1: cout<<"Inconsistency found after "<<line+1<<" relations."<<endl;
break;
case 2: cout<<"Sorted sequence cannot be determined."<<endl;
}
}
void mySort::checkOut(int entrance)
{
answer[0]=char(entrance+'A');
int array[27]={0};
int i=0;
for( i=25;i>=0;i--)
array[step[i]-1]=i;
for(i=1;i<chars;i++)
answer[i]=char(array[i]+'A');
}
int mySort::relationConfirmed()
{
if(step[right]<=step[left])
step[right]=step[left]+1;
return refreshStep(right);
}
int mySort::refreshStep(int entrance)
{
int flag=0;
if(step[entrance]==chars)
state=0;
else if(step[entrance] > chars)
{ state= 1;
return 1; }
set<int>::iterator ip,end=graph[entrance].outs.end();
for(ip=graph[entrance].outs.begin(); ip!=end; ip++)
{
if(step[*ip]<=step[entrance])
{ step[*ip]=step[entrance]+1;
flag=refreshStep(*ip); }
if(flag==1)
break;
}
return flag;
}
int main()
{
mySort test;
while(test.input())
{
test.compute();
test.print();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator