1395.cpp

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

#include<iostream>
#include<fstream>
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
using namespace std;
void dfs(vector<vector<int> > & vec, int p, int n, int d, int deep, int & f){
	if(deep==d){
		if(p==0) f=1;
		return;
	}
	else{
        for(int i=0;i<n;i++){
			if(f==1) return;
			if(vec[p][i]>=1){
               vec[p][i]-=1;vec[i][p]-=1;
			   dfs(vec,i,n,d,deep+1,f);
			   vec[p][i]+=1;vec[i][p]+=1;
			}
		}
	}
}
int main(){
    //ifstream cin("in.txt");
	string input,s;
	int m,n,i,j,d;
	while(getline(cin,input)&&input!="ENDOFINPUT"){
         istringstream ss(input);
		 ss>>s>>m>>n;
		 vector<int> temp(n,0);
		 vector<vector<int> > vec(n,temp);
		 d=0;
		 for(i=0;i<n;i++){
            getline(cin,s);
            istringstream is(s);
            while(is>>j) {d+=1;vec[i][j]+=1;vec[j][i]+=1;}
		 }
		 getline(cin,s);
		 int f=0;
		 dfs(vec,m,n,d,0,f);
		 if(f==1) cout<<"YES "<<d<<endl;
		 else cout<<"NO\n";
	}
}