Title translation:
Given N call records and a limit K. Each call record contains two names and a call time, and the people contacted belong to the same gang. The question requires that only a group with more than 2 people and a total call time exceeding K can be counted as a gang, and the person with the longest call time within the gang is the gang leader Boss.
Question solution ideas:
- Through two maps, the mutual mapping of name and id is completed to facilitate hash search.
- Then use a map to save the name of the leader and the number of gang members, and save the answer.
- The w[] array is used to save each person’s call time, and g[][] is used to save the weight of the edge, and it is convenient for DFS to find the gang.
- Find a new node with a larger w, point the head to this node, and become the new leader.
- totalweight to record the total call time of each gang. You must remember to traverse the edge first and accumulate the call time, and then delete this edge. On the one hand, this avoids the occurrence of loops, resulting in missing or repeated addition of edge weights.
Code:
And check the set:
#include <bits/stdc + + .h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 100;
const int M = N * 10;
const int mod = 1e9 + 7;
const double eps = 1e-9;
typedef pair<int, int> PII;
#define endl '\\
'
#define x first
#define y second
#define INF 0x3f3f3f3f
#define ls(k) k << 1
#define rs(k) k << 1 | 1
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int n, m, total;
unordered_map<string, int> num;
unordered_map<int, string> name;
map<string, int> ans;
vector<int> gang[N];
int p[N], w[N], k[N];
void create(string x)
{
if(!num[x])
{
num[x] = + + total;
name[total] = x;
}
}
int find(int x)
{
return p[x] == x ? x : p[x] = find(p[x]);
}
void merge(int a, int b, int t)
{
int fa = find(a), fb = find(b);
if(fa == fb)
{
k[fa] + = t;
return;
}
p[fa] = fb;
k[fb] + = k[fa] + t;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i + + ) p[i] = i;
for(int i = 1; i <= n; i + + )
{
string a, b;
int t;
cin >> a >> b >> t;
create(a), create(b);
w[num[a]] + = t;
w[num[b]] + = t;
merge(num[a], num[b], t);
}
for (int i = 1; i <= total; i + + ) gang[find(i)].push_back(i);
for (int i = 1; i <= total; i + + )
{
if(k[i] <= m || gang[i].size() <= 2) continue;
int head = i;
for (auto j : gang[i])
{
if(w[j] > w[head]) head = j;
}
ans[name[head]] = gang[i].size();
}
cout << ans.size() << endl;
for (auto i : ans) cout << i.first << " " << i.second << endl;
return 0;
}
DFS (Liu Shen):
#include <bits/stdc + + .h>
using namespace std;
const int maxn=2010;
const int inf=1e8;
map<string,int> nameToid;//name to number
map<int,string> idToname;//number to name
map<string,int> gang; //leader->number of people
int n,k,number=0; //Number of call records, minimum time, total number of people
int w[maxn]={0},G[maxn][maxn]={0};
bool vis[maxn]={false};
//Traverse nodes
void DFS(int now,int & amp;head,int & amp;gangnum,int & amp;totalweight){
gangnum + + ; //The number of members increases
vis[now]=true; //The current node has been visited
if(w[now]>w[head]){
head=now; //Find the point with the largest weight and become the new leader
}
for(int i=0;i<number; + + i){
if(G[now][i]>0){
totalweight + =G[now][i]; //Accumulate this edge
G[now][i]=G[i][now]=0; //Delete the edge between these two points
if(!vis[i]){ //If the next point has not been visited yet, visit it
DFS(i,head,gangnum,totalweight);
}
}
}
}
//Traverse the entire graph
void DFSTrave(){
for(int i=0;i<number; + + i){
if(!vis[i]){
int head=i,gangnum=0,totalweight=0; //Don’t forget to initialize
DFS(i,head,gangnum,totalweight);
if(gangnum>2 & amp; & amp; totalweight>k){
//gang saves the number of people corresponding to name
gang[idToname[head]]=gangnum;
}
}
}
}
//Complete the numbering of name and id for easy search
int change(string s){
//If found, there is no need to add the name
if(nameToid.find(s)!=nameToid.end()){
return nameToid[s];
}else{
nameToid[s]=number;
idToname[number]=s;
return number + + ;
}
}
int main(){
int weight;
cin>>n>>k;
string s1,s2;
for(int i=0;i<n; + + i){
cin >> s1 >> s2 >> weight;
int id1=change(s1);
int id2=change(s2);
w[id1] + =weight; //Save to the corresponding weight
w[id2] + =weight;
G[id1][id2] + =weight; //Save it into the adjacency matrix
G[id2][id1] + =weight;
}
DFSTrave();
cout << gang.size()<<"\\
";
//Because the map outputs keywords from small to large, there is no need to sort them.
map<string,int>::iterator it;
for(it=gang.begin();it!=gang.end(); + + it){
cout << it->first << " "<< it->second<<"\\
";
}
return 0;
}
Post another wrong question (I thought the name could only be in the same form like AAA, which ended up being that I could only pass two points)
#include<bits/stdc + + .h>
using namespace std;
map<char, int> p;
map<int, int> c;
int N, K;
int f[1010];
int find(int x)
{
if (x != f[x]) f[x] = find(f[x]);
return f[x];
}
struct node {
int num = 0, sum = 0, index = -1;
};
vector<node> m(26);
bool comp(node n1, node n2)
{
return n1.index < n2.index;
}
int main()
{
cin >> N >> K;
for (int i = 0;i < 26;i + + )
p['A' + i] = i;
for (int i = 0;i < 1010;i + + )
f[i] = i;
for (int i = 0;i < N;i + + )
{
string a, b;
int temp;
cin >> a >> b >> temp;
c[p[a[0]]] + = temp;
c[p[b[0]]] + = temp;
int x = find(p[a[0]]), y = find(p[b[0]]);
if (x != y) f[y] = x;
}
int cnt = 0;//Number of sets
for (int i = 0;i < m.size();i + + )
{
m[find(i)].num + + ;
m[find(i)].sum + = c[i];
if (m[find(i)].index == -1 || c[i] > c[m[find(i)].index])
m[find(i)].index = i;
}
sort(m.begin(), m.end(), comp);
for (int i = 0;i < 26;i + + )
{
if (m[i].num >= 3 & amp; & amp; m[i].sum > K*2)
cnt + + ;
}
cout << cnt << endl;
for (int i = 0;i < 26;i + + )
{
if(m[i].num >= 3 & amp; & amp; m[i].sum > K*2)
cout << char(m[i].index + 'A') << char(m[i].index + 'A') << char(m[i].index + 'A\ ') << " " << m[i].num << endl;
}
}
Pitfalls:
none