关联规则:FPgrowth算法

一.FP-growth算法原理:
其也是基于Apriori思想提出来的一共算法,但是其采用了一种高级的数据结构减少扫描次数,大大加快了算法速度。FP-growth算法只需要对数据库进行两次扫描,而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁,因此FP-growth算法的速度要比Apriori算法快。

二.算法流程:(样例
1.构建FP树
在构建FP树时我们需要对原始数据扫描两遍:
第一遍对所有元素项的出现次数进行计数,去掉不满足最小支持度的元素项
第二遍扫描中只需要考虑那些频繁元素,读入每个项集将其添加到一条已经存在的路径中,若该路径不存在则创建一条新路径。
2.从FP树中挖掘出频繁项集
从FP树中抽取频繁项集的三个步骤:
从FP树中获得条件模式基(以所查找元素项为结尾的路径集合,每一条路径都是一条前缀路径。 )
利用条件模式基,构建一颗条件FP树
迭代重复步骤(1),(2),直到树包含一个元素项为止

#include<stdio.h>
#include <cstdio>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<time.h>
#include<list>
using namespace std;

const int maxn = 10000; //输入记录条数的上界
const int sigmasize = 1000; //项的种类的上界
struct ListNode //Head Table中的节点
{
	int item; //项的名称
	int cnt; //项的计数
	ListNode() {
		item = 0;
		cnt = 0;
	}
	ListNode(int i, int c) //构造函数
			{
		item = i;
		cnt = c;
	}
};
struct TreeNode //FP Tree的节点
{
	int parent; //父亲节点的编号
	vector<int> child; //孩子节点的编号
	int cnt; //该节点的计数
	int item; //该节点项的名称
	TreeNode() {
		parent = 0;
		cnt = 0;
		item = 0;
		child.clear();
	}
	bool Empty() {
		if (parent == 0 && cnt == 0 && item == 0 && child.empty()) //判断节点是否为空节点
				{
			return true;
		}
		return false;
	}

};
TreeNode Copy(TreeNode t) //复制FP Tree的节点
		{
	TreeNode ret;
	ret.parent = t.parent;
	ret.cnt = t.cnt;
	ret.item = t.item;
	ret.child = t.child;
	return ret;
}
int tree[maxn][sigmasize]; //字典树,用来实现FP Tree
list<ListNode> database[maxn]; //原始数据库
list<ListNode> HeadTable; //项头表
int Count[maxn]; //原始数据库每一项的出现次数
int minsupportcnt; //最小支持度计数
int totalnum; //item的种类数
int num; //记录条数
int maxsz; //Tire树最多节点数
map<string, int> mp; //用于将string型的输入数据映射成int存储,以方便后续操作
int linenum; //原始数据库有多少条记录
string printitem(int t) //输出某个项,需要将int还原成原始数据库中的string
		{
	string s;
	for (map<string, int>::iterator it = mp.begin(); it != mp.end(); it++) {
		if (it->second == t) //first分量是string, second是int
				{
			s = it->first;
			return s;
		}
	}
	return s;
}
TreeNode* BuildTree(list<ListNode> a[], int num) //建立FP Tree,参数a为数据库,参数num为数据库记录数量
		{
	TreeNode Val[maxn]; //用数组存储数节点,可以通过每个节点的parent和child还原整个树,Val[0]存根节点
	memset(tree, 0, sizeof(tree));
	int sz = 1; //记录FP树的节点数
	for (int i = 0; i < num; i++) //遍历数据库中的所有记录
			{
		int u = 0; //添加某一条记录时要从根节点开始
		for (list<ListNode>::iterator it = a[i].begin(); it != a[i].end(); it++) //遍历每一条记录的所有项
				{
			ListNode t = *it;
			int c = t.item;
			if (tree[u][c] == 0) //如果u的孩子中没有c,则要添加新节点c
					{
				memset(tree[sz], 0, sizeof(tree[sz]));
				TreeNode tmp = TreeNode();
				tmp.cnt = t.cnt;
				tmp.item = c;
				tmp.parent = u;
				Val[sz] = tmp; //在Val[]中添加新节点,且新节点的编号是sz
				Val[u].child.push_back(sz); //u的孩子节点中要添加c
				tree[u][c] = sz++; //字典数中新建节点
			} else //如果u的孩子中有c,只要更新c的计数
			{
				for (int k = 0; k < Val[u].child.size(); k++) //遍历u的所有孩子
						{
					if (Val[Val[u].child[k]].item == c) {
						Val[Val[u].child[k]].cnt += t.cnt; //节点c计数+t.cnt
						break;
					}
				}
			}
			u = tree[u][c]; //往下走
		}
	}
	maxsz = sz; //更新FP Tree节点总数
	return Val; //返回FP Tree
}
void Input() {
	scanf("%d %d", &linenum, &minsupportcnt); //输入原始数据库中的记录条数和最小支持度计数
	int idx = 1; //将string型的项用int重新编号
	for (int i = 0; i < linenum; i++) {
		while (true) {
			string s;
			cin >> s;
			if (s == "0")
				break; //每一条记录末尾是0,表示该条记录输入完毕
			map<string, int>::iterator l_it;
			l_it = mp.find(s); //返回的是一个指针
			if (l_it == mp.end()) //如果该记录之前没有输入过,给该记录编号并放入database[i]中
					{
				database[i].push_back(ListNode(idx, 1));
				Count[idx]++;
				mp[s] = idx;
				idx++;
			} else //如果该记录之前输入过,直接增加其计数
			{
				database[i].push_back(ListNode(mp[s], 1));
				Count[mp[s]]++;
			}
		}
	}
	totalnum = idx; //记录项的种类总数
}
bool cmp(ListNode a, ListNode b) //用于将项头表中的项按个数从大到小排序
		{
	return a.cnt > b.cnt;
}
int priority[maxn]; //记录Head Table每个项的优先级
bool cmp2(ListNode a, ListNode b) //用于将条件模式基中的项按Head Table中的次序排序
		{
	int x = a.item;
	int y = b.item;
	if (priority[x] < priority[y]) //标记越小优先级越高,在head中cnt越大
		return true;
	return false;
}
void printlist(list<ListNode> head) //输出链表(用于调试)
		{
	for (list<ListNode>::iterator iter = head.begin(); iter != head.end();
			iter++) {
		string str = printitem((*iter).item);
		cout << str << " " << (*iter).cnt << endl;
	}
	cout << endl;
}
list<ListNode> BuildConditionalHeadTable(list<ListNode>*a, int n) //a为数据库,该函数为指针调用会改变a的值
		{
	int CondCount[maxn]; //记录a每个项的出现次数
	memset(CondCount, 0, sizeof(CondCount));
	list<ListNode> head; //项头表
	for (int i = 0; i < n; i++) //遍历a中每个项
			{
		list<ListNode>::iterator iter = a[i].begin();
		for (iter; iter != a[i].end(); iter++) {
			ListNode t = *iter;
			int c = t.item;
			CondCount[c] += t.cnt; //记录a中每个项的出现次数
		}
	}
	for (int i = 0; i < totalnum; i++) {
		if (CondCount[i] < minsupportcnt)
			continue;
		head.push_back(ListNode(i, CondCount[i])); //如果某个项出现次数满足最小支持度计数,则把它加入项头表中
	}
	head.sort(cmp); //将项头表按照每个项出现次数从大到小排序
	memset(priority, 0, sizeof(priority));
	int pir = 0;
	for (list<ListNode>::iterator iter = head.begin(); iter != head.end();
			iter++) {
		ListNode t = *iter;
		int c = t.item;
		priority[c] = pir++; //priority[c]记录项c在Head Table中的优先级(出现次数越多优先级越高),priority[c]值越小在cmp2中越优先
	}
	for (int i = 0; i < n; i++) {
		list<ListNode>::iterator iter = a[i].begin();
		for (iter; iter != a[i].end();) {
			ListNode t = *iter;
			int c = t.item;
			if (CondCount[c] < minsupportcnt) //删除数据库a中出现次数小于最小支持度计数的项
					{
				a[i].erase(iter++);
			} else {
				iter++;
			}
		}
		a[i].sort(cmp2); //将a[i]中的项按照在Head Table的出现次数从大到小排序
	}
	return head; //返回项头表
}
void FP_Growth(list<ListNode> transrecords[], list<ListNode> patternbase, int n) //使用FP Tree,通过模式增长挖掘频繁模式
		{ //transrecords[]是数据库,patternbase是条件模式基,n是数据库记录条数
	list<ListNode> head = BuildConditionalHeadTable(transrecords, n); //通过数据库构建项头表
	TreeNode *val;
	val = BuildTree(transrecords, n); // 构建FP-Tree
	TreeNode tmpval[maxn]; //在之后的递归调用会改变val的值,所以要用tmpval保存现场
	int tmpmaxsz = maxsz; //在之后的递归调用会改变maxsz的值,所以要用tmpmaxsz保存现场
	for (int i = 0; i < maxsz; i++) {
		tmpval[i] = Copy(val[i]);
	}
	if (val[0].Empty()) // 如果FP-Tree为空则返回
	{
		return;
	}
	if (!patternbase.empty()) //输出项头表的每一项+postPattern
	{
		for (list<ListNode>::iterator iter = head.begin(); iter != head.end();
				iter++) {
			ListNode t = *iter;
			string str = printitem(t.item); //需要将int还原成原始数据库中的string
			int cnt = t.cnt;
			for (list<ListNode>::iterator it = patternbase.begin();
					it != patternbase.end(); it++) {
				str += "\t" + printitem((*it).item); //加上条件模式基
			}
			cout << str << " " << cnt << endl;
		}
	}
//对项头表中的每一个节点,构造其条件模式基与条件FP Tree
	for (list<ListNode>::reverse_iterator iter = head.rbegin();
			iter != head.rend(); iter++) //反向遍历Head Table(从小到大)
			{
		ListNode t = *iter;
		list<ListNode> newpostpattern; //新的条件模式基
		newpostpattern.push_back(ListNode(t.item, t.cnt)); //新的条件模式基中先加入项头表当前项
		if (!patternbase.empty()) //如果之前的条件模式基不为空,则合并
		{
			list<ListNode> tmp = patternbase;
			newpostpattern.merge(patternbase, cmp);
			patternbase = tmp;
		}
		list<ListNode> newdatabase[maxn]; //条件数据库
		int id = 0;
		for (int i = 0; i < maxsz; i++) {
			if (val[i].item == t.item) //在当前FP Tree中找到所有项为t.item的节点
					{
				for (int pre = val[i].parent; pre != 0; pre = val[pre].parent) //由parent从下往根节点遍历,找出前缀路径
						{
					newdatabase[id].push_back(
							ListNode(val[pre].item, val[i].cnt)); //将路径中的每个节点加入新数据库中
//注意前缀路径中的每个节点的计数都更新为当前项的计数,即t.cnt
				}
				id++;
			}
		}
		FP_Growth(newdatabase, newpostpattern, id); //由新的数据库和新的条件模式基递归调用,在条件FP Tree中继续挖掘频繁模式
//恢复现场
		maxsz = tmpmaxsz;
		for (int i = 0; i < maxsz; i++) {
			val[i] = Copy(tmpval[i]);
		}
	}
}
void run() {
	Input();
	list<ListNode> patternbase = list<ListNode>(); //第一次由原始数据库构建FP Tree时,后缀项集初始化为空链表
	FP_Growth(database, patternbase, linenum); //用FP Tree递归挖掘频繁模式
}
int main() {
	printf("Author: I-Hsin\n\n");
	freopen("test.txt", "r", stdin);
//freopen("Test4.txt","r",stdin);
//freopen("Test5.txt","r",stdin);
	run();
	return 0;
}
//输入样例:(文件读入,每一条记录末尾添上0作为该条记录的结束标志)
//9 3
//牛奶 鸡蛋 面包 薯片 0
//鸡蛋 爆米花 薯片 啤酒 0
//鸡蛋 面包 薯片 0
//牛奶 鸡蛋 面包 爆米花 薯片 啤酒 0
//牛奶 面包 啤酒 0
//鸡蛋 面包 啤酒 0
//牛奶 面包 薯片 0
//牛奶 鸡蛋 面包 黄油 薯片 0
//牛奶 鸡蛋 黄油 薯片 0

 

0

关联规则:Apriori算法

一.Apriori原理:

如果某个项集是频繁的那么它的所有子集也是频繁的,即一个项集值非频繁集,那么它的所有超集也是非频繁的。Apriori算法是用来发现频繁项集的一种方法,该算法的参数为最小支持度和数据集.

二.求解频繁项集的算法流程:

  • 生成所有单个物品的项集列表
  • 扫描交易记录查看哪些项集满足最小支持度要求,去除不满足的集合
  • 生成包含两个元素的项集列表
  • 重新扫描交易记录,去掉不满足最小支持度的项集
  • 重复进行知道所有的项集都被去掉

三.从频繁项集中挖掘出关联规则(利用置信度进行剪枝)

原理:如果某条规则不满足最小可信度要求,那么该规则的所有子集也不会满足最小可信度要求。

算法流程:

  • 从一个频繁项集开始,接着创建一个规则列表,其中规则的后件只包含一个元素
  • 然后对这些规则进行测试,去除不满足最小可信度要求的规则
  • 合并所有剩余规则来创建一个新的规则列表,其中规则的后件包含两个元素。
  • 然后重复执行上面的步骤

C++实现:(转载自:http://blog.csdn.net/scjthree/article/details/39963831)

#include<iostream>
#include<set>
#include<map>
#include<string>
#include<vector>
using namespace std;
typedef map<set<string>, int> map_s; //string表示项,int表示支持度

map_s Ck; //候选集Ck
map_s Lk; //频繁项集Lk
vector<set<string> > data; //原始数据
vector<set<string> > L; //频繁项集合
vector<string> data2; //分割后的原始数据
int n, m;
int minSup = 2;
int minConf = 0.2;
set<string> s;
string in;
void Delete(map_s &Ck) //删除不满足最小支持度的项
		{
	for (map_s::iterator l_it = Ck.begin(); l_it != Ck.end();) {
		if (l_it->second < minSup) {
			l_it = Ck.erase(l_it);
		} else
			l_it++;
	}
}

int compset(set<string> s1, set<string> s2) {
	int flag = 0;
//判断集合s1是不是s2的子集
	for (set<string>::iterator it = s1.begin(); it != s1.end(); it++) {
//s1有元素不在s2中
		if (s2.find(*it) == s2.end()) {
			flag = 10;
			break;
		}
	}
	for (set<string>::iterator it = s2.begin(); it != s2.end(); it++) {
//s2有元素不在s1中
		if (s1.find(*it) == s1.end()) {
			flag += 1;
			break;
		}
	}
	/*当flag==0,s1元素全部在s2中,s2元素也全部在s1中,s1==s2
	 当flag==10,s1有元素不在s2中,s2所有元素都在s1中,s1包含了s2
	 当flag==1,s1所有元素在s2中,s2有元素不在s1中,s2包含了s1
	 当flag==11,s1 s2集合互不包含
	 */
	return flag;
}

map_s apriori_gen(map_s &Ck, int k) //参数为最小支持度(全局变量)和数据集,k为利用k-1项频繁集进行剪枝
		{
//生成子集
	map_s Ck_temp;
	set<string> s_temp;
	for (map_s::iterator l_it1 = Ck.begin(); l_it1 != Ck.end(); l_it1++) //************************连接
			{
		for (map_s::iterator l_it2 = Ck.begin(); l_it2 != Ck.end(); l_it2++) {
//如果两个set一样,则说明是同一个KEY,跳过
			if (!((l_it1->first > l_it2->first) || (l_it1->first < l_it2->first)))
				continue;
//否则开始组装,遍历整个Ck
			for (set<string>::iterator s_it = l_it2->first.begin();
					s_it != l_it2->first.end(); s_it++) {
//如果该值在l_it1 set里面可以找到,不能组装
				if (l_it1->first.find(*s_it) != l_it1->first.end())
					continue;
//否则进行组装,先把l_it1的set复制进去
				s_temp = l_it1->first;
//再把l_it2的值放进去,set刚好可以去重
				s_temp.insert(*s_it);
//无需判断该组装的set是否已在生成,map容器去重
				Ck_temp.insert(make_pair(s_temp, 0));
			}
		}
	}

//k==2 需要扫描原始数据得出计数值
	if (k == 2) {
		for (map_s::iterator l_it = Ck_temp.begin(); l_it != Ck_temp.end();
				l_it++)
			for (int i = 0; i < data.size(); i++) //l_it集合被data[i]完整包含,则计数值+1
				if ((10 == compset(data[i], l_it->first))
						|| (0 == compset(data[i], l_it->first)))
					Ck_temp[l_it->first]++;

//扫描完之后排除 非频繁项
		for (map_s::iterator l_it = Ck_temp.begin(); l_it != Ck_temp.end();)
			if (Ck_temp[l_it->first] < minSup)
				l_it = Ck_temp.erase(l_it);
			else
				l_it++;
	}
//如果是大于2的情况,扫描k-1的频繁项子集
	if (2 < k) //******************************************剪枝
			{
//每次都循环获取每个Ck的k-1子集元素
//如{I1,I2,I3}C3的子集是{I1,I2} {I2,I3} {I3,I4}
//如果Ck的子集不在k-1的频繁项子集中,则去掉该Ck项
		for (map_s::iterator l_it = Ck_temp.begin(); l_it != Ck_temp.end();) {
			int flag;
			for (set<string>::iterator s_it = l_it->first.begin();
					s_it != l_it->first.end(); s_it++) {
//开始求子集
//首先把当前Ck项的集合保存
				s_temp = l_it->first;
//去掉一个元素,即是它的k-1子集
				s_temp.erase(*s_it);
//遍历频繁项集合L,看看是不是在频繁集中
				flag = 1;
				for (int i = 0; i < L.size(); i++) {
//如果K-1子集在频繁项集中存在,则保留
					if (0 == compset(s_temp, L[i])) {
						flag = 0;
						break;
					}
				}
//如果找到了哪怕一个k-1子集项不在频繁项集中,直接退出
				if (flag)
					break;
			}
//只有所有的k-1子集在频繁项集中,才保留该Ck项
			if (flag)
				l_it = Ck_temp.erase(l_it);
			else
				l_it++;
		}
		for (map_s::iterator l_it = Ck_temp.begin(); l_it != Ck_temp.end();
				l_it++)
			for (int i = 0; i < data.size(); i++) //l_it集合被data[i]完整包含,则计数值+1
				if ((10 == compset(data[i], l_it->first))
						|| (0 == compset(data[i], l_it->first)))
					Ck_temp[l_it->first]++;
	}

	if (Ck_temp.empty())
		return Ck_temp;
	cout << "由L" << k - 1 << "产生的候选集C" << k << " " << "支持度计数" << endl;
	for (map_s::iterator l_it = Ck_temp.begin(); l_it != Ck_temp.end();
			l_it++) {
		for (set<string>::iterator s_it = l_it->first.begin();
				s_it != l_it->first.end(); s_it++)
			cout << *s_it << " ";
		cout << " " << l_it->second << endl;
	}
	return Ck_temp;
} //参数为

int main() {
	cout << "请输入事务,第一行输入事务数。每行第一个值输入该事务的item数:" << endl;
//生成原始数据集
	cin >> n;
	for (int i = 0; i < n; i++) {
		s.clear();
		cin >> m;
		for (int j = 0; j < m; j++) {
			cin >> in;
			s.insert(in);
			data2.push_back(in);
		}
		data.push_back(s);
	}
//扫描数据集D,生成C1
//对于每个候选集里面的元素
	for (int j = 0; j < data2.size(); j++) {
		int flag = 1; //如果C1中存在该元素,计数值加1
		for (map_s::iterator l_it = Ck.begin(); l_it != Ck.end(); l_it++) {
			if ((l_it->first).find(data2[j]) != (l_it->first).end()) {
				Ck[l_it->first]++;
				flag = 0;
				break;
			}
		}
//不存在,插入到C1集合中
		if (flag) {
			s.clear();
			s.insert(data2[j]);
			Ck.insert(pair<set<string>, int>(s, 1));
		}
	}
//去掉支持度不足的
	for (map_s::iterator l_it = Ck.begin(); l_it != Ck.end();) {
		if (l_it->second < minSup)
			l_it = Ck.erase(l_it);
		else
			l_it++;
	}
	cout << "C1候选集:" << endl;
	cout << "项集" << " " << "支持度计数" << endl;

	for (map_s::iterator l_it = Ck.begin(); l_it != Ck.end(); l_it++) {
		for (set<string>::iterator s_it = (l_it->first).begin();
				s_it != (l_it->first).end(); s_it++)
			cout << *s_it << " " << l_it->second << endl;
	}
	int f_count = 2;
	while (f_count) { //将Ck内的k-1频繁集全部保存到L集中
		for (map_s::iterator l_it = Ck.begin(); l_it != Ck.end(); l_it++)
			L.push_back(l_it->first);
//获取Ck集,已清除掉小于支持度的候选集
		Ck = apriori_gen(Ck, f_count);
		if (Ck.empty())
			break;
		else
			f_count++;
	}
	cout << "过程中产生的所有频繁项集:" << endl;
	for (int i = 0; i < L.size(); i++) {
		for (set<string>::iterator s_it = L[i].begin(); s_it != L[i].end();
				s_it++)
			cout << *s_it << " ";
		cout << endl;
	}

}
/*
 input:
 4
 3 I1 I2 I6
 4 I1 I2 I3 I5
 3 I2 I3 I7
 5 I1 I3 I5 I6 I2
 */
/*
 output:
 C1候选集:
 项集 支持度计数
 I1 3
 I2 4
 I3 3
 I5 2
 I6 2
 由L1产生的候选集C2 支持度计数
 I1 I2 3
 I1 I3 2
 I1 I5 2
 I1 I6 2
 I2 I3 3
 I2 I5 2
 I2 I6 2
 I3 I5 2
 由L2产生的候选集C3 支持度计数
 I1 I2 I3 2
 I1 I2 I5 2
 I1 I2 I6 2
 I1 I3 I5 2
 I2 I3 I5 2
 由L3产生的候选集C4 支持度计数
 I1 I2 I3 I5 2
 过程中产生的所有频繁项集:
 I1
 I2
 I3
 I5
 I6
 I1 I2
 I1 I3
 I1 I5
 I1 I6
 I2 I3
 I2 I5
 I2 I6
 I3 I5
 I1 I2 I3
 I1 I2 I5
 I1 I2 I6
 I1 I3 I5
 I2 I3 I5
 I1 I2 I3 I5
 */

 

0

1053. Path of Equal Weight (30)-PAT甲级真题(普通树的遍历,保存dfs路径)

原题:https://www.patest.cn/contests/pat-a-practise/1053

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1100;
int n, m, s, path[maxn];
struct node {
	int weight; //点权
	vector<int> child; //每个(此题为非叶子)节点的孩子
} Node[maxn];
bool cmp(int a, int b) //注意类型int
		{
	return Node[a].weight > Node[b].weight; //按孩子结点的weeight从大到小排序
}
void dfs(int index, int numnode, int sum) //当前节点,路径节点个数,总权值
		{
	cout << "*" << index << "*" << endl;
	if (sum > s)
		return;
	if (sum == s) {
		if (Node[index].child.size() != 0) //还没到叶子结点
			return;
		for (int i = 0; i < numnode; i++) //到达叶子结点,进行输出
				{
			cout << Node[path[i]].weight;
			if (i < numnode - 1)
				cout << " ";
			else
				cout << endl;
		}
		return;
	}
	for (int i = 0; i < Node[index].child.size(); i++) //枚举所有子结点//不同于原版dfs { int child=Node[index].child[i]; path[numnode]=child;//将结点child加入path dfs(child,numnode+1,sum+Node[child].weight);//递归进入下一层 } } int main() { cin>>n>>m>>s;
		for (int i = 0; i < n; i++) {
			cin >> Node[i].weight;
		}
	int id, k, child;
	for (int i = 0; i < m; i++) {
		cin >> id >> k;
		for (int j = 0; j < k; j++) {
			cin >> child;
			Node[id].child.push_back(child);
		}
		sort(Node[id].child.begin(), Node[id].child.end(), cmp);
	}
	path[0] = 0; //路径的第一个结点设置为0号结点
	dfs(0, 1, Node[0].weight);
	return 0;
}

 

0

1034. Head of a Gang 图的遍历,DFS

原题:https://www.patest.cn/contests/pat-a-practise/1034

1034. Head of a Gang (30)
One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:

Name1 Name2 Time

where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.

Output Specification:

For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.

Sample Input 1:
8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
Sample Output 1:
2
AAA 3
GGG 3
Sample Input 2:
8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
Sample Output 2:
0

题目大意:给出1000条以内的通话记录A B和权值w,和阈值k,如果一个团伙人数超过2人并且通话总权值超过k,令团伙里面的自身权值的最大值为头目,输出所有满足条件的团伙的头目,和他们团伙里面的人数
分析:总的来说是一个判断一个图的连通分量的个数,用图的遍历解决,深度优先遍历。
1.因为给的是字母,要用两个map把它们转换成数字,从1开始排列命名所有不同的人的id,存储在两个map里面,一个字符串对应id,一个id对应字符串,方便查找,正好顺便统计了总共的人数idNumber。
2.建立两个数组,weight和G,分别存储每条边的权值和每个结点的权值,因为这两个题目中都要求得后判断。
3.用传递引用的方法深度优先dfs,这样传入的参数在dfs后还能保存想要求得的值
4.遍历过一条边之后就把这条边的权值设为0( G[u][v] = G[v][u] = 0;)防止出现回路遍历死循环

#include<iostream>
#include<map>
#include<string>
using namespace std;
const int maxn = 2010, INF = 1000000000;
map<int, string> int2string;
map<string, int> string2int, gang; //gang:head->人数
int vis[maxn], g[maxn][maxn], weight[maxn], n, k, numperson; //总人数numperson

void dfs(int nowvisit, int &head, int &nummember, int &totalvalue) //totalvalue为连通块的总边权
		{
	nummember++;
	vis[nowvisit] = 1;
	if (weight[nowvisit] > weight[head])
		head = nowvisit;
	for (int i = 0; i < numperson; i++) {
		if (g[nowvisit][i] > 0) {
			totalvalue += g[nowvisit][i];
			g[nowvisit][i] = g[i][nowvisit] = 0; //防止回头
			if (vis[i] == 0)
				dfs(i, head, nummember, totalvalue);
		}

	}
}
void dfstravel() {
	for (int i = 0; i < numperson; i++) {
		if (vis[i] == 0) {
			int head = i, nummember = 0, totalvalue = 0;
			dfs(i, head, nummember, totalvalue);
			if (nummember > 2 && totalvalue > k)
				gang[int2string[head]] = nummember;
		}
	}
}
int change(string str) {
	if (string2int.find(str) != string2int.end())
		return string2int[str];
	else {
		string2int[str] = numperson;
		int2string[numperson] = str;
		return numperson++;
	}
}
int main() {
	int tm;
	string a, b;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a >> b >> tm;
		int id1 = change(a);
		int id2 = change(b);
		weight[id1] += tm;
		weight[id2] += tm;
		g[id1][id2] += tm; //打电话属于无向图
		g[id2][id1] += tm;
	}
	dfstravel();
	cout << gang.size() << endl;
	for (map<string, int>::iterator it = gang.begin(); it != gang.end(); it++) {
		cout << it->first << " " << it->second << endl;
	}
	return 0;
}

 

0