2014“华为杯”苏、鲁高校大学生程序设计大赛总决赛【通讯录】
题目描述:
WenX最近从很多知名网站中获取到了用户的个人信息（像邮箱啦，电话号码啦等等），他希望能够计算每个用户在所有这些网站的购物总金额（这样他就可以对购物总金额较高的一批人推送广告啦！）
不幸的是，他发现很多人有不止一个手机或者邮箱（特别是他所面向的有钱人），有的人喜欢在不同的网站使用不同的手机号或者邮箱进行注册。因此他希望能够将不同记录中手机或者邮箱的用户关联起来。
WenX获取的每条记录包括三个属性：邮箱、电话号码、购买金额。可以认为不同记录中包含相同邮箱的是（现实世界中的）同一个人；同理包含相同电话号码的也是（现实世界中的）同一个人。
WenX希望能够输入一个电话号码或者邮箱，返回这个电话号码或邮箱的所有者在这些记录中至少消费了多少钱。
需要注意的是，电话号码中由于各个网站的记录不统一，所以如果电话号码中包含了国家区号的号码可以认为与不包含国家区号的号码是同一个号码。（因为是国内网站，所以可以假设并不会遇到外国的电话号码，可以认为包含了国家区号的号码指的是以0086 或+86 开头的电话号码，输入样例保证不会出现以“00” 开头但不以“0086” 开头的电话号码或以“+”开头但不以“+86” 开头的电话号码）。
对不包含国家区号的号码，国内区号以0开头（如北京为010，010-10086是一个北京的电话号码）。而对于包含国家区号的号码，国家区号后接国内区号需要将前导0去掉，有一些号码如手机号码等本来就不包括地区区号的号码，接国家区号时不需要去掉任何的字符。同时，根据不同网站显示的风格不同，电话号码中可能包含一些用于显示的分隔符，包括'-'，'_'以及左右半角括号。
下面的电话号码可以认为是同一个电话号码：
0086-25-5209-0000
(+86)2552090000
025-5209-00-00
(025)5209_0000
下面的电话号码可以认为是同一个电话号码：
0086-138-2222-2222
(+86)13822222222
138-2-2-2-2-2-2-2-2
请注意电子邮箱不区分大小写。
输入:
输入数据的第一行是一个整数T，表示测试样例数目。随后包含T个测试样例。
每个测试样例首先包括一行，里面包括两个数字M，N，分别表示记录条数和查询次数随后包括M行，每行中包括两个字符串stel，semail以及一个整数购物金额c，以空格分隔，表示一个用户在某个网站中登记了电话号码stel以及邮箱semail并产生了金额为c的消费。
随后包括N行，每行包括一个字符串（这个字符串可能为手机号码或者为邮箱地址），表示需要查询的用户。
其中0≤M,N≤1000，0≤c≤10000000。
输入数据保证所有电话号码和邮箱的长度均小于1000。
输出:
对每个测试样例，你应该输出N+1行。
首先，输出一行``Case #t:''，随后输出N行，分别表示每个查询的用户的消费总额。
样例输入:
1
5 2
0086-25-5209-0000 1@seu.edu.cn 10
(+86)2552090000 2@seu.edu.cn 20
025-5209-00-00 3@seu.edu.cn 20
(025)5209_0000 1@seu.edu.cn 20
138222222222222 1@seu.edu.cn 10
1@seu.edu.cn
122-_-222222222222
样例输出:
Case #1:
80
0
问题分析:
该题与DG之社团调查都具有病毒扩散的特点，电话号码和email相同的为同一个人，可仿照DG来做，不同点是遍历图的时候是遍历强连通图的所有边，将边的权值相加即为消费金额，效率略低，就不贴了。
接下来说的是另一个方法合并法
简单来说就是将属于同一个人的所有电话和email放入一个容器中（一个容器即代表一个人），每次输入一个电话和email存在如下五种情况：
①：已存在的容器中不存在该电话和email
则取一新容器将电话和email放入，该容器对应消费金额为c；
②：已存在的容器中存在该电话，不存在该email
则将该email放入该容器中，该容器对应消费金额加c；
③：已存在的容器中存在该email，不存在该电话
则将该电话甘露该容器中，该容器对应消费金额加c；
④：已存在的容器中存在该电话和email，且该容器为同一容器
则该容器对应消费金额加c；
⑤：已存在的容器中存在该电话和email，且该容器不为同一容器
则将其中一个容器中的电话和email放入另一容器中，该容器置空，另一个容器对应消费金额变为两容器消费金额总和加c；
操作结束后，只需知道输入的电话号码或email属于哪个容器即可知道对应消费金额
java实现如下：
<pre><code>
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
// 电话号码处理函数
static String phone(String str) {
str = str.replaceAll("[-_()]", "");
if (str.substring(0, 2).equals("00"))
str = str.substring(4);
else if (str.charAt(0) == '+')
str = str.substring(3);
else if (str.charAt(0) == '0')
str = str.substring(1);
return str;
}
// 查找目标字符串所属集合
static int search(String tar, Set<String>[] set, int len) {
for (int i = 0; i < len; i++) {
if (set[i].contains(tar))
return i;
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
int m = sc.nextInt(), n = sc.nextInt(), len = 0;
sc.nextLine();
Set<String>[] set = new HashSet[m];
long[] sign = new long[m];
for (int j = 0; j < m; j++) {
String[] strarr = sc.nextLine().split("\\s");
String p = phone(strarr[0]);
String e = strarr[1].toLowerCase();
long c = Long.parseLong(strarr[2]);
int index1 = search(p, set, len);
int index2 = search(e, set, len);
if (index1 == -1 && index2 == -1) {
set[len] = new HashSet();
set[len].add(p);
set[len].add(e);
sign[len] = c;
len++;
} else if (index1 == -1 && index2 != -1) {
set[index2].add(p);
sign[index2] += c;
} else if (index1 != -1 && index2 == -1) {
set[index1].add(e);
sign[index1] += c;
} else if (index1 == index2) {
sign[index1] += c;
} else {
set[index1].addAll(set[index2]);
sign[index1] += (sign[index2] + c);
set[index2].clear();
}
}
System.out.println("Case #" + (i + 1) + ":");
for (int j = 0; j < n; j++) {
String check = sc.nextLine();
if (check.contains("@")) {
check = check.toLowerCase();
int index = search(check, set, len);
if (index != -1)
System.out.println(sign[index]);
else
System.out.println(0);
} else {
check = phone(check);
int index = search(check, set, len);
if (index != -1)
System.out.println(sign[index]);
else
System.out.println(0);
}
}
}
}
}
</code></pre>
