joj 1016: Degrees of separation

http://acm.jlu.edu.cn/joj/showproblem.php?pid=1016
按照六度空间理论，你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。这就是六度空间理论，也叫小世界理论。
这道题就是告诉你每一个人他认识的人，然后给出两个人之间的间隔，这个间隔就是至少通过几个人认识另一个人。

这个题显然是一个图论的题目，就是求两顶点之间的最短距离，但是比较不易处理的是：这个题开始没有列出所有的顶点，而是直接给出边的信息，这对构造邻接矩阵需要一些处理.
构造完邻接矩阵直接使用floyd算法就可以了。

#include<iostream>
#include<string>
#include<vector>
#include<map>
using namespace std;
const int MAX_DEG = 100000;

struct LineInfo{
	string person;
	int connect_num;
	vector<string> connect_persons;
};

void floyd( vector< vector<int> > & distances ){
	int i, j, k;
	int n = distances.size();
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			for(k = 0; k < n; k++){
				int t_dis = distances[i][k] + distances[k][j];
				if(distances[i][j] > t_dis)
					distances[i][j] = t_dis;
			}
}


int main(){
	int n,n_query;
	cin >> n;
	int i,j;
	map<string,int> person_to_index;
	vector< vector<int> > matrix;
    vector<LineInfo> lines;

	for(i = 0; i < n; i++){
		LineInfo line;
		cin >> line.person >> line.connect_num;
		
		for(j = 0; j < line.connect_num; j++){
			 string connect_person;
			 cin >> connect_person;
			 line.connect_persons.push_back(connect_person);
		}

		lines.push_back(line);
		person_to_index[line.person] = i;
		vector<int> v;
		for(j = 0; j < n; j++){
			v.push_back(MAX_DEG);
		}

		matrix.push_back(v);
	}

	for(i = 0; i < n; i++){
		LineInfo line = lines[i];
		string one = line.person;
		int num = line.connect_num;
		for(int i = 0; i < num; i++){
			int idex,jdex;
			idex = person_to_index[one];
			jdex = person_to_index[line.connect_persons[i]];
			matrix[idex][jdex] = 1;
		}
	}

	floyd(matrix);
	
	cin >> n_query;
	for(i = 0; i < n_query; i++){
		string p1,p2;
		cin >> p1 >> p2;
		int p1_index = person_to_index[p1];
		int p2_index = person_to_index[p2];
		if(matrix[p1_index][p2_index] == MAX_DEG){
			cout << p1 << " has no connection to " << p2 << "." << endl;
		}else{
			cout << p1 << " is separated from " << p2 << " by "
				 << matrix[p1_index][p2_index] - 1 << " degrees." << endl;
		}
	}
	return 0;	
}

我比较懒，由于这个题构造邻矩阵比较容易，由于数据量不是很大，所以开始使用BFS，时间应该没问题，但是老是WA,不知道什么原因:

#include<iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;

map< string,vector<string> > mp;
map< string, bool > visited;

void BFS(string tp1,string tp2){
	queue<string> qu;
	qu.push(tp1);
	int distance = 0;

	while(!qu.empty()){
		string p = qu.front();
		qu.pop();
		vector<string> v = mp[p];
		int i = 0;
		for(; i < v.size(); i++){
			if( tp2 == v[i] ){
				cout << tp1 << " is separated from " << tp2
					 << " by " << distance << " degrees." << endl;
				return;	
			}
			if( visited.count(v[i]) == 0 )	{
				qu.push(v[i]);
				visited[v[i]] = true;
			}
		}
		distance++;
	}

	cout << tp1 << " has no connection to " << tp2 << "." << endl;
}

int main(){
	int n,ncase;
	string onePerson, knownTheOther;
	int nknown;

	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> onePerson;
		vector<string> v;
		mp[onePerson] = v;
		cin >> nknown;
		for(int i = 0; i < nknown; i++){
			cin >> knownTheOther;
		    mp[onePerson].push_back(knownTheOther);
		}
	}
	
	cin >> ncase;
	string tp1,tp2;
	for(int i = 0; i < ncase; i++){
		cin >> tp1 >> tp2;
                  visited.clear();
		BFS(tp1,tp2);
	}
}

评论

2 楼 yjyongz 2010-07-06  

#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;

map< string,vector<string> > mp;
map<string,bool> visited;

void BFS(string name1,string name2)
{
	queue<string> qu;
	qu.push(name1);
	int dis[10];
	int distance = 0,k=0;
	bool find = false;
	while(!qu.empty())
	{	
		int size = qu.size();
		for(int j=0;j<size;j++)
		{
			string tp1 = qu.front();
			visited[tp1] = true;
			qu.pop();
			vector<string> vec = mp[tp1];
			for(int i=0;i<vec.size();i++)
			{
				if(name2==vec[i])
				{	
					
					find = true;
					dis[k] = distance;
					k++;
				}
				if(visited.count(vec[i])==0)
				{
					visited[vec[i]] = 1;//visited
					qu.push(vec[i]);
				}
			}
		}
		distance++;
	}
	if(!find)
		cout<<name1<<" has no connection to "<<name2<<"."<<endl;
	else
	{
		int small=10000;
		for(int i=0;i<k;i++)
			if(small>dis[i])
				small = dis[i];
		cout<<name1<<" is separated from "<<name2<<" by "<<small<<" degrees."<<endl;
	}
	return;
}
int main()
{
	int persons;
	cin>>persons;
	for(int i=0;i<persons;i++)
	{
		string name; 
		cin>>name;
		int nKnown;
		cin>>nKnown;
		vector<string> v;
		mp[name] = v;
		for(int j=0;j<nKnown;j++)
		{
			string knowOther;
			cin>>knowOther;
			mp[name].push_back(knowOther);
		}
	}
	int nCase;
	cin>>nCase;
	for(int i=0;i<nCase;i++)
	{
		string name1,name2;
		cin>>name1>>name2;
		BFS(name1,name2);
		visited.clear();
	}
	return 0;
}

1 楼 yjyongz 2010-07-06  

#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;

map< string,vector<string> > mp;
map<string,bool> visited;

void BFS(string name1,string name2)
{
queue<string> qu;
qu.push(name1);
int dis[10];
int distance = 0,k=0;
bool find = false;
while(!qu.empty())
{
int size = qu.size();
for(int j=0;j<size;j++)
{
string tp1 = qu.front();
visited[tp1] = true;
qu.pop();
vector<string> vec = mp[tp1];
for(int i=0;i<vec.size();i++)
{
if(name2==vec[i])
{

find = true;
dis[k] = distance;
k++;
}
if(visited.count(vec[i])==0)
{
visited[vec[i]] = 1;//visited
qu.push(vec[i]);
}
}
}
distance++;
}
if(!find)
cout<<name1<<" has no connection to "<<name2<<"."<<endl;
else
{
int small=10000;
for(int i=0;i<k;i++)
if(small>dis[i])
small = dis[i];
cout<<name1<<" is separated from "<<name2<<" by "<<small<<" degrees."<<endl;
}
return;
}
int main()
{
int persons;
cin>>persons;
for(int i=0;i<persons;i++)
{
string name;
cin>>name;
int nKnown;
cin>>nKnown;
vector<string> v;
mp[name] = v;
for(int j=0;j<nKnown;j++)
{
string knowOther;
cin>>knowOther;
mp[name].push_back(knowOther);
}
}
int nCase;
cin>>nCase;
for(int i=0;i<nCase;i++)
{
string name1,name2;
cin>>name1>>name2;
BFS(name1,name2);
visited.clear();
}
return 0;
}