1220.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<iostream>
#include<sstream>
#include<vector>
#include<string>
using namespace std;
class item{
public:
	string name;
	vector<string> mname;
	item(){}
};
int main(){
   string input,from,to,temp,mutation;
   vector<string> inputmutation;
   vector<item> vec;
   vec.push_back(item());
   vec[0].name="ADAM";
   int l,i,j,k;
   while(getline(cin,input)&&input!=""){
	  inputmutation.clear();
      istringstream is(input);
	  is>>mutation>>to>>mutation>>from>>mutation;
	  if(mutation=="mutating") while(is>>temp) inputmutation.push_back(temp);
	  //*********************有没有跟adam有关系******************************
	  for(i=0;i<vec.size();i++) if(from==vec[i].name) break;
	  if(i==vec.size()){cout<<"clone "<<to<<" from "<<from<<" has no connection to ADAM\n";continue;}
	  //*********************有关系，并且是I*********************************
	  item newitem; newitem.name=to; k=0;//判断是否不安全
	  for(l=0;l<inputmutation.size();l++){
		  newitem.mname.push_back(inputmutation[l]);
          for(j=0;j<vec[i].mname.size();j++){
			  if(inputmutation[l]==vec[i].mname[j]){k=1;temp=inputmutation[l];
				  break;
			  }
		  }
		  if(k==1) break;
	  }
      if(k==0){
		  newitem.mname.insert(newitem.mname.begin(),vec[i].mname.begin(),vec[i].mname.end());
		  vec.push_back(newitem);
	  }
	  if(k) cout<<"clone "<<to<<" from "<<from<<" was at least twice mutated with "<<temp<<endl;
	  else cout<<"clone "<<to<<" from "<<from<<" is consistent and safe\n";
   }
}