当前位置：首页 > 编程日记 > 正文

1034 Head of a Gang(图的DFS解法) 擦边大法好

编程日记 2024-09-06 15:50:00

1.题目的大意是给出很多人(结点)之间的通话记录，每两人之间的权重取决于他俩通话权重的总时长，如果一个社区的人数超过2且社区内发生的通话总时长超过给定阈值，那么这属于一个社区。最后要求输出社区的总数，再按照社区头目的姓名字母序从小到大输出头目姓名和社区人数。

2. DFS的注意点，这是我第一次写图的DFS。根据教材给的总结出需要两个函数：DFS(int no,int socNo)和DFStraver()，由后者调用前者，至于参数是根据实际情况决定的。配套还要有一个布尔数组vis[maxn]来记录每一个点是否被访问过。

3.vis[maxn]的修改发生在DFS(int no,int socNo)内部，第一句话就是。被用到是在DFStraver()的进入搜索之前。一般来说在DFS(int no,int socNo)的内部，开始遍历当前节点的所有邻接结点时，一是要判断是不是邻接结点，而是要判断该邻接节点是否被访问过。但是本题我起初这么做的时候，发现第三个社区就没有被当作社区，输出权重才发现该社区的总权重被算出是50。如图所示

why?一定是FFF和HHH之间的那条边没算进权重，究其原因，该社区的进入结点是FFF，第二个是GGG，第三个是HHH，但是当HHH开始遍历其子节点的时候，会发现唯一的子节点FFF（GGG和HHH之间的边已经被擦除）被访问过了。所以FFF和HHH之间那条边自然也就不会但算进去。怎么解决呢？自然是要把遍历子节点前判断是否已经访问过的条件给删掉。

void DFS(int no,int socNo){//传入人的编号和社区编号 vis[no] = true;//处理社区头目问题 int headNo = social[socNo].head;if(wper[no]>wper[headNo])social[socNo].head = no;//处理社区人数问题social[socNo].pers.insert(no);for(int i=0;i<totalNum;i++){if(adj[no][i]!=0){//处理社区权重问题social[socNo].totalWei += adj[no][i];//擦掉加入过的这条边adj[no][i] = adj[i][no] = 0; DFS(i,socNo);}} 
}void DFStraver(){for(int i=0;i<totalNum;i++){if(vis[i]==false){DFS(i,socNum);if(social[socNum].pers.size()>2&&social[socNum].totalWei>thre)validNum++;socNum++;}}
}

4. 但是当我删掉，新的问题来了，这样FFF这个结点会被算作两次，导致社区三的节点总数被记作了4。于是我想到集合的去重功能，不再在社区结构体设置人数这一变量，而是设置set<int>来记录编号，调用size()函数得到人数。

struct Social{int head = maxn;//社区的头头set<int> pers;//人的编号 int totalWei = 0;//总权重 
}social[maxn];

5. 在记入一条边的权重后，记得将这条边删除(我也是看参考书才知道)，但是注意了这是无向图，邻接矩阵中的两个相互对称的位置都记录了这条边，所以抹零两个数。

6. 下面的三剑客是方便将string和int互相映射，不是哈希那种哦，注意学习

map<string,int> strToIntMp;//姓名从字符串映射到编号map<int,string> intToStrMp;//姓名从编号映射到字符串int archive(string s){if(strToIntMp.find(s)!=strToIntMp.end())return strToIntMp[s];//说明这个人已经存档过了//如果没有，要先确定他是第几号 int num = strToIntMp.size();//两个映射集是同步的 strToIntMp[s] = num;intToStrMp[num] = s;return num; 
}

7. 急性子与慢性子

最后唠叨一点细枝末节。可以让代码结构更清晰。

急性子：由于是每个社区权重最大的那个人做头头，所以开了一个int数组，存放每个人的权重，这个和邻接矩阵一样，一边读入一边就该加上了。

int wper[maxn] = {0};//每个人的权重
for(int i=0;i<n;i++){cin>>p1>>p2>>ct;no1 = archive(p1);no2 = archive(p2);wper[no1] += ct;wper[no2] += ct;adj[no1][no2] += ct; adj[no2][no1] += ct;
}

慢性子：我一开始没注意到要输出真正的社区(达到了那两条要求)的个数，想着设置一个统计总的社区个数的全局变量socNum就好了，最后排好序再把不合格的给过滤掉。但是亡羊补牢也为时未晚，再设置一个统计真正的社区数的全局变量validNum，这个也在DFStraver()中，每次结束一个新社区的遍历后更新。可以见得，过滤放最后也没关系。

void DFStraver(){for(int i=0;i<totalNum;i++){if(vis[i]==false){DFS(i,socNum);if(social[socNum].pers.size()>2&&social[socNum].totalWei>thre)validNum++;socNum++;}}
}

AC代码

#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
typedef long long LL;using namespace std;const int maxn = 2010;int wper[maxn] = {0};//每个人的权重bool vis[maxn] = {false};//是否被遍历到 int adj[maxn][maxn] = {0};//邻接矩阵(本题是无向图) map<string,int> strToIntMp;//姓名从字符串映射到编号map<int,string> intToStrMp;//姓名从编号映射到字符串int archive(string s){if(strToIntMp.find(s)!=strToIntMp.end())return strToIntMp[s];//说明这个人已经存档过了//如果没有，要先确定他是第几号 int num = strToIntMp.size();//两个映射集是同步的 strToIntMp[s] = num;intToStrMp[num] = s;return num; 
} int n,thre;//call-num,threshold
int totalNum;//总人数 struct Social{int head = maxn;//社区的头头set<int> pers;//人的编号 int totalWei = 0;//总权重 
}social[maxn];int socNum = 0;//社区个数 
int validNum = 0;//有效社区数 void DFS(int no,int socNo){//传入人的编号和社区编号 vis[no] = true;//处理社区头目问题 int headNo = social[socNo].head;if(wper[no]>wper[headNo])social[socNo].head = no;//处理社区人数问题social[socNo].pers.insert(no);for(int i=0;i<totalNum;i++){if(adj[no][i]!=0){//处理社区权重问题social[socNo].totalWei += adj[no][i];//擦掉加入过的这条边adj[no][i] = adj[i][no] = 0; DFS(i,socNo);}} 
}void DFStraver(){for(int i=0;i<totalNum;i++){if(vis[i]==false){DFS(i,socNum);if(social[socNum].pers.size()>2&&social[socNum].totalWei>thre)validNum++;socNum++;}}
}bool cmp(Social a,Social b){return intToStrMp[a.head]<intToStrMp[b.head];
} int main(){scanf("%d %d",&n,&thre);string p1,p2;//person1 person2int no1,no2;//上面两个人的编号 int ct;//call timefor(int i=0;i<n;i++){cin>>p1>>p2>>ct;no1 = archive(p1);no2 = archive(p2);wper[no1] += ct;wper[no2] += ct;adj[no1][no2] += ct; adj[no2][no1] += ct;}//进行深度优先搜索totalNum = strToIntMp.size();//总人数DFStraver();sort(social,social+socNum,cmp);//按照头头的姓名字母序从小到大排序 //输出有效社区总数 printf("%d\n",validNum);for(int i=0;i<socNum;i++){if(social[i].pers.size()>2&&social[i].totalWei>thre){cout<<intToStrMp[social[i].head];printf(" %d\n",social[i].pers.size());} } return 0;
}

https://www.dkcj.cn/info/17556.html

1034 Head of a Gang(图的DFS解法) 擦边大法好

相关文章：

Android定位方式和测试方法

vue el-form鼠标事件导致页面刷新解决方案；vue 阻止多次点击提交数据通用方法...

[转]wxODBC(wxWidgets)中使用驱动程序方式打开数据库

1076 Forwards on Weibo

2014年个人工作总结

DAL(数据库访问层)

Navicat for Oracle

1013 Battle Over Cities(图的DFS解法)

你必须了解的微服务架构设计的10个要点！

企业信息化中常见决策点应对

WebView调试

1013 Battle Over Cities(并查集解法)

FastDFS为什么要结合Nginx？

STL容器[34]

企业可视化报表工具选型经验分享

1003 Emergency(Dijkstra，Bellman-Ford，SPFA三种解法)

存储过程4-前台

安卓学习-其他-文件读写

X5同层播放器应用实践

1007 Maximum Subsequence Sum(两种思路)

C#学习-EF在三层中使用

各大IT公司笔试真题汇总开发人员一定要加入收藏夹的网站(收藏)

Python编写Hive UDF

1045 Favorite Color Stripe(LIS解法)

5.8fork父子进程

word表格自动编号

Vue API(directives) 自定义指令

1045 Favorite Color Stripe(LCS解法) 需再理解

C++ primer第五版随笔--2015年1月6日

Python性能分析指南——中