2021/08/16 20:34
思路:DFS,字符串,哈希,并查集,离散化
题意:给出以 name1 name2 time 的通话记录,只要进行了通话,就认定这两人有关系,关系具有传递性。一个帮派需要符合两个条件,首先帮派人数大于2,帮派内通话总时间大于k,帮派头目为帮派内通话时长最长的人,现在需要输出帮派个数,并按照字典序输出各帮派头目姓名
真猛阿,我还以为图论题目全是dijkstra呢
乍一看需要用并查集,因为里面涉及到了关系的传递,但是初始化是个问题,也能做,把姓名进行转化为数字,每次合并的时候维护每个帮派的人数,帮派内部的头目,应该可以做出来,等下写一下
这道题直接DFS求解也是可的,只不过需要哈希,名字映射一个人和时长,直接dfs就可以找到一个帮派的人,要注意,因为同一条边存了两次,所以计算的时间需要除以2,比如说A B 2,A给B打了两分钟,会存下两次,A给B打,B给A打,求解出了根据条件判断帮派,存入答案,排序输出即可
2021/08/16 21:54
写了一手并查集,真猛阿,字符串映射的地方写反了,疯狂debug,我都准备对拍了,发现函数写错了
果然并查集是能写出来的,就当练一手了,但是用并查集写比DFS慢了一点,空间也要多十倍左右
大致是这样的,首先把字符串映射成26进制数,注意这里需要开26^4
的数组,大致是50w
(就是因为这里空间会多很多)
然后先把边存下来,因为每个人的通话时间在输入过程中没办法计算出来,所以得先计算每个人的时间,这样方便维护每个集合的根节点,维护成帮派头目,也就是通话时间最长的那个人。然后依次遍历每条边进行合并,注意当两个结点的根节点不同时,需要维护两个结点的通话时间和人数,即便二者根节点相同也需要把两个结点间的通话时间加进来,因为即便是在同一集合也会有多条边,这里需要把每一条边都加上
2021/09/02 13:31
发现并查集的空间占用太大了,需要大约50w
,万一字符串并不一定是固定位数,长度随机呢,再大一点可能数组就存不下了
并且看到,数据范围最多给出1000
条通话记录(这里可能会有2000
个人,发现数据bug,已提交工单),1000和50w相差了500倍,这样把字符串转数字实在是划不来,空间利用率0.2%
,所以说我们可以通过离散化,把离散的数据变成连续的,通过哈希表映射,映射到0-2000
,可以大大地减少空间的浪费,我们可以先用unordered_set存下所有的字符串,然后依次遍历这个容器,依次将字符串映射到0-2000
并查集(离散化)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
const int N = 2010;
struct Edge
{
string a;
string b;
int t;
};
int n, k;
bool st[N];
vector<Edge> edges;
vector<string> names;
unordered_set<string> s;
unordered_map<string, int> mp;
int f[N], total[N], cnt[N], t[N];
void init()
{
for(int i = 0; i < N; i++)
f[i] = i, cnt[i] = 1;
}
int find(int x)
{
return f[x] = f[x] == x ? x : find(f[x]);
}
void merge(int x, int y, int w)
{
int fx = find(x), fy = find(y);
if(total[fx] < total[fy])
swap(fx, fy);
f[fy] = fx;
if(fx != fy)
t[fx] += t[fy], cnt[fx] += cnt[fy];
t[fx] += w;
}
int main()
{
init();
cin >> n >> k;
for (int i = 0; i < n; i ++ )
{
string n1, n2;
int t;
cin >> n1 >> n2 >> t;
s.insert(n1), s.insert(n2);
edges.push_back({n1, n2, t});
}
for(auto &str : s)
{
mp[str] = names.size();
names.push_back(str);
}
for (auto &e : edges)
{
int a = mp[e.a], b = mp[e.b];
st[a] = true, st[b] = true;
total[a] += e.t, total[b] += e.t;
}
for (auto &e : edges)
merge(mp[e.a], mp[e.b], e.t);
set<pair<string, int>> ans;
for (int i = 0; i < N; i ++ )
{
if(st[i] && f[i] == i)
{
if(cnt[i] > 2 && t[i] > k)
ans.insert({names[i], cnt[i]});
}
}
cout << ans.size() << endl;
for(auto t : ans)
cout << t.first << ' ' << t.second << endl;
return 0;
}
并查集代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int N = 5e5; //26^4
struct Edge
{
int a;
int b;
int t;
};
int n, k;
bool st[N];
vector<Edge> edges;
int f[N], total[N], cnt[N], t[N];
int get(string s)
{
int res = 0;
for (int i = 2, j = 1; i >= 0; i--, j *= 26)
res += (s[i] - 'A') * j;
return res;
}
string tostring(int x)
{
string s;
for (int i = 0; i < 3; i ++ )
{
s = char('A' + x % 26) + s;
x /= 26;
}
return s;
}
void init()
{
for(int i = 0; i < N; i++)
f[i] = i, cnt[i] = 1;
}
int find(int x)
{
return f[x] = f[x] == x ? x : find(f[x]);
}
void merge(int x, int y, int w)
{
int fx = find(x), fy = find(y);
if(total[fx] < total[fy])
swap(fx, fy);
f[fy] = fx;
if(fx != fy)
t[fx] += t[fy], cnt[fx] += cnt[fy];
t[fx] += w;
}
int main()
{
init();
cin >> n >> k;
for (int i = 0; i < n; i ++ )
{
string n1, n2;
int t;
cin >> n1 >> n2 >> t;
int a = get(n1), b = get(n2);
st[a] = true, st[b] = true;
total[a] += t, total[b] += t;
edges.push_back({a, b, t});
}
for (auto e : edges)
merge(e.a, e.b, e.t);
set<pair<string, int>> ans;
for (int i = 0; i < N; i ++ )
{
if(st[i] && f[i] == i)
{
if(cnt[i] > 2 && t[i] > k)
ans.insert({tostring(i), cnt[i]});
}
}
cout << ans.size() << endl;
for(auto t : ans)
cout << t.first << ' ' << t.second << endl;
return 0;
}
DFS代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
int n, k;
unordered_map<string, vector<pair<string, int>>> G;
unordered_map<string, int> total;
unordered_map<string, bool> vis;
int dfs(string name, vector<string> &names)
{
vis[name] = true;
names.push_back(name);
int sum = total[name];
for(auto e : G[name])
if(!vis[e.first])
sum += dfs(e.first, names);
return sum;
}
int main()
{
cin >> n >> k;
while (n -- )
{
string a, b;
int t;
cin >> a >> b >> t;
G[a].push_back({b, t});
G[b].push_back({a, t});
total[a] += t;
total[b] += t;
}
vector<pair<string, int>> ans;
for(auto t : G)
{
string name = t.first;
if(vis[name])
continue;
vector<string> names;
int sum = dfs(name, names) / 2;
if(sum > k && names.size() > 2)
{
string head = names[0];
for(auto t : names)
if(total[head] < total[t])
head = t;
ans.push_back({head, (int)names.size()});
}
}
sort(ans.begin(), ans.end());
cout << ans.size() << endl;
for(auto t : ans)
cout << t.first << ' ' << t.second << endl;
return 0;
}