按题意模拟即可,注意要选用高效的数据结构来存储信息和查询以避免超时,具体参考代码和注释
#include <iostream>
#include <set>
#include <queue>
#include <unordered_map>
const int N = 100010;
struct Event { // 用以表示一个到期额度的事件
int ts, v1, v2, val; // 到期时间,到期的边的两点,应减去的额度
bool operator<(const Event &o) const {
return ts > o.ts; // 大根堆
}
};
struct Dot { // 图结点
struct Edge {
int w, v; // 权值,终点
bool operator>(const Edge &o) const {
return o.w != w ? w > o.w : v < o.v; // 按权值降序,点编号升序
}
};
std::unordered_map<int, int> we; // 记录当前点所有边的权值
std::set<Edge, std::greater<Edge>> sr; // 主要对象排名
} g[N]; // 图
std::priority_queue<Event> evs; // 存事件
int is, pa; // 通信孤岛和通信对数量
int n, m;
int mobj[N]; // 每个点的主要通信对象,初始为0表示无
void incr(int u, int v, int w)
{ // u到v的边权值加w
auto &d = g[u];
auto it = d.we.find(v);
if (it == d.we.end()) { // 添加一条新边
if (d.we.empty()) is--; // 当前点为孤岛
d.we[v] = w;
d.sr.insert({w, v});
} else {
d.sr.erase({it->second, v}); // 找到并删除原有边
it->second += w; // 加上新边的权值
d.sr.insert({it->second, v}); // 插入新边
}
// 处理通信对数量
// 说明:对于每次添加权值操作而言,如果当前点先前位于通信对中,但更新后不位于,则通信对数要减一
// 反之如果先前不位于但更新后位于则通信对数量需要加一,如果更新前后状态一致则保持不变
int t = mobj[mobj[u]] == u ? -1 : 0; // 更新边权前,当前点是否位于通信对中
mobj[u] = d.sr.begin()->v; // 更新主要通信对象
t += mobj[mobj[u]] == u ? 1 : 0; // 更新后是否位于通信对中
pa += t; // 更新通信对数量
}
void decr(int u, int v, int w)
{ // u到v点的边权值减w
auto &d = g[u];
auto it = d.we.find(v);
d.sr.erase({it->second, v});
int ori = mobj[u]; // 原主要通信对象
it->second -= w; // 减去额度
if (it->second <= 0) { // 边额度为0,删除边
d.we.erase(v);
if (d.we.empty()) is++, mobj[u] = 0; // 当前点变为了孤岛
else mobj[u] = d.sr.begin()->v; // 更新主要通信对象
} else {
d.sr.insert({it->second, v}); // 插入新边
mobj[u] = d.sr.begin()->v;
}
// 更新通信对数量,此处逻辑与上面完全一致
int t = mobj[ori] == u ? -1 : 0;
t += mobj[mobj[u]] == u ? 1 : 0;
pa += t;
}
int main()
{
scanf("%d%d", &n, &m);
is = n; // 初始全部为通信孤岛
for (int i = 1, k, a, b, c, d; i <= m; i++) { // 枚举天数
scanf("%d", &k);
while (k--) {
scanf("%d%d%d%d", &a, &b, &c, &d);
// 机器a和机器b的每日额度加c,持续d天
incr(a, b, c), incr(b, a, c);
evs.push({i + d, a, b, c}); // 添加一个d天后到期的事件
}
// 处理当前天的所有到期事件
while (!evs.empty() && evs.top().ts == i) {
auto [_, u, v, val] = evs.top();
evs.pop();
decr(u, v, val), decr(v, u, val);
}
// 查询
scanf("%d", &k);
while (k--) {
scanf("%d", &a);
printf("%d\n", mobj[a]); // 输出主要通信对象
}
scanf("%d%d", &a, &b);
if (a) printf("%d\n", is);
if (b) printf("%d\n", pa);
}
return 0;
}