1119my.cpp

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

#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
void run(vector<vector<int> > & vec,int n,vector<int> & use,int & t,int deep,int p){
	 int i,j;
	 //cout<<deep<<" "<<p<<endl;
	 if(deep==1){
		 for(i=1;i<=n;i++){
             if(vec[i].size()&&use[i]==0){
			   t+=1;
			   use[i]=1;
               for(j=0;j<vec[i].size();j++){
                  if(use[vec[i][j]]==0){
                     use[vec[i][j]]=1;
				     run(vec,n,use,t,deep+1,vec[i][j]);
				  }
			   }
			 }
		 }
	 }
	 else{
		 for(j=0;j<vec[p].size();j++){
                  if(use[vec[p][j]]==0){
                     use[vec[p][j]]=1;
				     run(vec,n,use,t,deep+1,vec[p][j]);
				  }
		 }
	 }
}
int main(){
	//ifstream cin("in.txt");
    int f,t,c=1,i,j,n;
	while(cin>>f&&f){
		if(c>1) cout<<endl;
        n=0;
		cin>>t;
		if(n<f) n=f; if(n<t) n=t;
		vector<int> temp; vector<vector<int> > vec(1100); 
		if(f!=t){
			vec[f].push_back(t); vec[t].push_back(f);}
		//cout<<f<<" "<<t<<endl;
		while(cin>>f&&f){
            cin>>t;
			if(n<f) n=f; if(n<t) n=t;
			if(f!=t){
				vec[f].push_back(t); vec[t].push_back(f);}
			//cout<<f<<" "<<t<<endl;
		}
		f=0;
		cout<<"Network #"<<c++<<endl;
		for(i=1;i<=n;i++){
            if(vec[i].size()==0) continue;
			t=0;
		    temp=vec[i];
			vec[i].clear();
			vector<int> use(n+1,0);
			use[i]=use[0]=1;
			run(vec,n,use,t,1,0);
			vec[i]=temp;
			//cout<<t<<endl;
			if(t>=2){
               f=1;
			   cout<<"  SPF node "<<i<<" leaves "<<t<<" subnets\n";
			}
		}
		if(f==0) cout<<"  No SPF nodes\n";
	}
}