首页 > ACM题库 > HDU-杭电 > HDU 4039-The Social Network-字典树-[解题报告]HOJ
2015
04-16

HDU 4039-The Social Network-字典树-[解题报告]HOJ

The Social Network

问题描述 :

The social network system (SNS) helps people to keep connecting with their friends. Every user in SNS has a friends list. The user can read news posted by the users in his friends list. Friend relation is symmetric – if A is a friend of B, B is always a friend of A.

Another important function in SNS is friend recommendation. One effective way to recommend friends is recommend by mutual friends. A mutual friend between two users A and B, is a user who is a friend of both A and B. A user can not be a friend of himself. For a specific user A, the system will recommend the user who is not himself or his friend, and has mutual friends with A. If more than one such user exists, recommend the one has most mutual friends with A. If still a tie exists, output all of them.

输入:

The first line is a integer T (T≤100), the number of test case.
The beginning of each test case is two integers N and Q, the number of friend relationship and the number of query. 1 ≤ N, Q ≤ 1000
The following N lines each contain two different names separated by a single space. Each name consisted by only lowercase letters, and its length is less than or equal to 15. This means the two users are friends. No friend relationship will be given more than once.
The following Q lines each describe a query. Each line contain one user name. The data guarantee that this name appears at least once in above N lines.

输出:

The first line is a integer T (T≤100), the number of test case.
The beginning of each test case is two integers N and Q, the number of friend relationship and the number of query. 1 ≤ N, Q ≤ 1000
The following N lines each contain two different names separated by a single space. Each name consisted by only lowercase letters, and its length is less than or equal to 15. This means the two users are friends. No friend relationship will be given more than once.
The following Q lines each describe a query. Each line contain one user name. The data guarantee that this name appears at least once in above N lines.

样例输入:

1
10 11
hongshu digua
yingying hongshu
xmm hongshu
huaxianzi xmm
tangjiejie huaxianzi
xhmz yingying
digua xhmz
zt tangjiejie
xmm lcy
notonlysuccess ljq
hongshu
digua
yingying
xmm
huaxianzi
tangjiejie
xhmz
zt
lcy
notonlysuccess
ljq

样例输出:

Case 1:
xhmz
yingying
digua
digua tangjiejie yingying
hongshu lcy zt
xmm
hongshu
huaxianzi
hongshu huaxianzi
-
-

http://acm.hdu.edu.cn/showproblem.php?pid=4039
The
36th ACM/ICPC Asia Regional Chengdu Site —— Online Contest

1009

题意:模拟一个社交网络系统,先给你n个朋友关系,对每个人,系统会推荐给他一些人给他交朋友,系统推荐的是他朋友的朋友,而且只推荐他最多个朋友的朋友,如果会推荐多个,按照字典序从小到大输出,如果一个也不推荐输出“-”。。。1 ≤ N, Q ≤ 1000

分析:由于数据量小,直接暴力即可,找他所有的朋友的朋友只需要n^2即可,二重for循环搞定,为节省时间,用邻接表存,因为每个人是以名字形式给出的,用字典树做一个映射。。。注意一个小地方,就是a的朋友的朋友可能是a的朋友。。。

代码:其实就是一水题,只是rank排在前面了,贴出来玩玩。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

const int N=2010;
int n, q, up, num;
char s[20], s1[20];
struct trie
{
	int a[26];
	int num;
	void init()
	{
		memset(a, -1, sizeof(a));
		num = -1;
	}
} t[10000];
vector<int> a[N];
vector<int>::iterator it, it1;
int cnt[N], flag[N], flag1;
struct node
{
	int i;
	char s[16];
} ss[N], ss1[N];

inline int insert(char *s)
{
	int p=0;
	while(*s)
	{
		if(t[p].a[*s-'a']==-1)
		{
			t[up].init();
			t[p].a[*s-'a'] = up++;
		}
		p = t[p].a[*s-'a'];
		s++;
	}
	if(t[p].num==-1)
	{
		t[p].num = num++;
		flag1 = 1;
	}
	return t[p].num;
}
inline int query(char *s)
{
	int p=0;
	while(*s)
	{
		if(t[p].a[*s-'a']==-1)
			return -1;
		p = t[p].a[*s-'a'];
		s++;
	}
	return t[p].num;
}
int cmp(const node &a, const node &b)
{
	return strcmp(a.s, b.s)<0;
}

int main()
{
	int i, j, cas, cas1, x, y, mx;
	
	scanf("%d", &cas);
	for(cas1=1; cas1<=cas; cas1++)
	{
		scanf("%d%d%d", &n, &q);
		t[0].init();
		up = num = 1;
		for(i=1; i<=n; i++)
		{
			scanf("%s %s", s, s1);
			flag1 = 0;
			x = insert(s);
			if(flag1==1)
				strcpy(ss[x].s, s);
			flag1 = 0;
			y = insert(s1);
			if(flag1==1)
				strcpy(ss[y].s, s1);
			a[x].push_back(y);
			a[y].push_back(x);
		}
		printf("Case %d:\n", cas1);
		while(q--)
		{
			scanf("%s", s);
			for(i=1; i<num; i++)
				cnt[i] = 0;
			x = query(s);
			mx = 0;
			for(i=1; i<num; i++)
				flag[i] = 0;
			flag[x] = 1;
			for(it=a[x].begin(); it!=a[x].end(); it++)
				flag[*it] = 1;
			for(it=a[x].begin(); it!=a[x].end(); it++)
			{
				y = *it;
				for(it1=a[y].begin(); it1!=a[y].end(); it1++)
				{
					if(flag[*it1]==0)
					{
						cnt[*it1]++;
						if(cnt[*it1]>mx)
							mx = cnt[*it1];
					}
				}
			}
			if(mx==0)
			{
				printf("-\n");
				continue;
			}
			up = 0;
			for(i=1; i<num; i++)
			{
				if(cnt[i]==mx)
				{
					strcpy(ss1[up].s, ss[i].s);
					up++;
				}
			}
			sort(ss1, ss1+up, cmp);

			printf("%s", ss1[0].s);
			for(i=1; i<up; i++)
				printf(" %s", ss1[i].s);
			printf("\n");
		}
		
		for(i=1; i<num; i++)
			while(!a[i].empty())
				a[i].pop_back();
	}

	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ggggiqnypgjg/article/details/6767844


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。