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);
}
}
分享到:
相关推荐
joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考
Joj 以与 JDOM 提供 XML 的 Java 表示类似的方式提供 Java 源代码的 Java 对象表示。
在JOJ上做的一些ACM试题,都通过在线测试。
本程序能实现操作系统中的先进先出页面置换算法
一些题目解答 1001-1012 自己做的,希望能帮助到一些朋友
可以为在JOJ上练习的同学做入门使用,这些代码全部通过。
joj acm 源代码,即一些题得答案,方便大家联系参考。加油吧。
Etre au courant quand JoJ est en live,策划人semaine et liens vers lesréséauxauxsocioaux Soyez au courant纠结JoJ开始à流光! 现场直播将继续进行。 约翰·奎因·伊斯特·布鲁和克林·德集团的非官方网站 D...
吉林大学 joj 1000-2645题代码,嘿嘿,大家就不用在花JPOINT买代码了,祝ACMer实现自己的心愿
硬币转化问题。用动态规划解决,不是很难。
这个题其实现在想起来也不知道是怎么就给ac的。
整理的ACM题集,吉林大学的,pdf格式,jilin univercity online judge system
关于大数取模的运算,比如说:a^b%m。下面提供2种解法。
插件 :star: Jovo插件插件使您可以轻松扩展Jovo Framework,而不必弄乱其核心代码和体系结构。 查看以了解如何创建自己的插件。插件清单要将您的插件添加到下表中,请分叉存储库,然后以与其他插件相同的格式将您的...
该mod基于荒木飞吕彦的JoJo的奇妙冒险漫画和动漫系列。 这个mod也受到KnightDemon的1.12 mod 极大启发。 这个mod的目的是要从专营权中尽可能多地增加Minecraft,该mod目前仅包含Stand能力,其他能力(Hamon,...
Este Projeto签证是由estoque进行的,它是由mer mercadorias uma determinada empresa sejam averiguadas和atualizadas ... 2021年1月20日,由JoséCláudiodeAraújoJúnior和Annielly Ferreira de Sousa所设计。
furystudios 普尔维·扎达塔克(Prvi zadatak) ...DroppingOff - radnikhodajućidolazi做pripadajuće科萨雷(izvedeno kroz provjeru tagova kutije)我卡达joj JE dovoljno blizu,fizičkiJE lan
大智慧最新安装包,老的已经过期不能查询个人自选股,所以推荐最新的大智慧给大家安装