题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int n, k;
unordered_map<string, vector<pair<string, int>>> g;
unordered_map<string, int> total;
unordered_map<string, bool> st;
int dfs(string ver, vector<string> &nodes)
{
st[ver] = true;
nodes.push_back(ver);
int sum = 0;
for (auto &edge : g[ver])
{
sum += edge.second;
string cur = edge.first;
if (!st[cur]) sum += dfs(cur, nodes);
}
return sum;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
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>> res;
for (auto item : total)
{
string ver = item.first;
vector<string> nodes;
int sum = dfs(ver, nodes) / 2;
if (nodes.size() > 2 && sum > k)
{
string boss = nodes[0];
for (string node : nodes)
if (total[boss] < total[node])
boss = node;
res.push_back({boss, (int)nodes.size()});
}
}
sort(res.begin(), res.end());
cout << res.size() << endl;
for (auto item : res) cout << item.first << ' ' << item.second << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla