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