CSP202203_4
题目
思路
首先分析题目的大致要求。
简化的题干就是，给定 n 个点和 m 次操作。每次操作中会对两点 u、v 建立一条无向边，该边同时具有两个信息，分别为边权以及存在时间。
对点 u 的询问操作，在所有与 u 相连的点中，是否存在 v 使边 (u, v) 为 u 所有边中的最大权值边。
查询图中孤立点数，查询满足点 u、v 的连边同时为两点最大权值边的点对数。
点、边、询问都是1e5的级别，时间复杂度要求较高。
首先想如何打暴力。直接 vector 存图。每次操作前，遍历所有边，将无效边删除(不一定是删，也可能是修改边权)，再维护新加入的边，更新所有点的度以及对应点的最大权值边。
询问最大权值边和孤立点数量可以在维护后直接 \(O(1)\) 查询，而查询点对需要再遍历所有点一次，\(O(n)\)。显然时间复杂度期望 \(O(nm)\) ，稳定超时。
考虑如何优化。每次更新无效边时，遍历整个图显然会有大量的无效操作，对此能否优化？
- 以边的失效时间建边记录权值与端点，每次查询前修改边时可以直接 \(O(1)\) 定位到失效的所有边。
再考虑具体的修改操作。针对点 u 的所有边遍历到对应的 v，如果使用 vector 进行存储，每次查询需腰遍历所有邻接点，若为完全图时间复杂度为\(O(n)\)。使用 set 维护的话为，基于红黑树的查询可以在\(O(logn)\)下完成。具体实现方面，直接使用 NODE 型的 set 存储节点信息即可。
总体思路如上，具体分析一下更新的整个操作。
- 针对 u、v 节点，以 u 作为当前节点，如果 u 为孤立点，则直接建对应的新边即可。
- 否则，在 u 所有邻接点中查找，如果已经存在边 (u, v)，更新对应边权。若不存在 v，则同样直接加入新边即可。
- 因为在边的修改过程中 u 的孤立点以及点对性质都可能该边，因此修改前先修改对应的数量使其不包含 u，在修改后再重新确定 u 是否符合条件。
关于孤立点以及点对的查询实现，孤立点即对应的 set 为空或者第一条边边权为0。注意后者不要忘记，在对已存在边更新边权长度时，边权为 0 的边没有删除，不额外判断会导致计算错误(当然也可以在插边时直接判断)。点对同理直接按照题意模拟判断即可，同理因为存在0权边，要特判一下点是否为孤立点。
在实际写的时候，想着用 set 优化查询，结果写着写着就当成成 vector 了，又是使用迭代器整个遍历了一次。交上去只有20pts，时间复杂度卡的确实好紧。
重新改用 set 直接 find，结果突然意识到查询要查的是一个结构体，而更新时只知道 v，只能再额外存储所有边的边权供查询，使用 map 直接记录边权，与边的修改同步更新。
在更新操作中，map 的查询和 set 的 find 调用都是\(O(logn)\)，总时间复杂度为\(O(mlogn)\)。
按照上述写法，提交AC，开了快读用时1.718s，也是够极限了qwq。
大晚上的写的好乱，抽空再完善完善
Code
#include<bits/stdc++.h>
#define ll long long
const int INF = 0x3f3f3f3f;
using namespace std;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x*f;
}
struct EDGE
{
int from, to;
ll dis;
};
struct NODE
{
int to;
ll dis;
bool operator < (const NODE &a) const
{
if(this->dis != a.dis) return this->dis > a.dis;
else return this->to < a.to;
}
/*bool operator == (const NODE &a) const
{
return this->to == a.to;
}*/
};
int n, m;
int iso_cnt, pat_cnt;
set <NODE> node[200010];
vector <EDGE> edge[200010];
map < pair<int, int>, ll > mp;
bool is_iso(int u)
{
if(node[u].empty()) return true;
if(! node[u].begin()->dis) return true;
return false;
}
bool is_pat(int u)
{
if(is_iso(u)) return false;
set <NODE> :: iterator it = node[u].begin();
if(is_iso(it->to)) return false;
else
{
if(node[it->to].begin()->to == u) return true;
else return false;
}
}
void Upd(int u, int v, int w)
{
if(is_iso(u)) iso_cnt--;
if(is_pat(u)) pat_cnt--;
if(node[u].empty())
{
//cout << "New" << endl;
NODE tmp = {v, w};
node[u].insert(tmp);
mp[make_pair(u, v)] = w;
}
else
{
bool flag = true;
set <NODE> :: iterator it = node[u].find({v, mp[make_pair(u, v)]});
if(it == node[u].end())
{
//cout << "New" << endl;
NODE tmp = {v, w};
node[u].insert(tmp);
mp[make_pair(u, v)] = w;
}
else
{
//cout << "Cor" << endl;
NODE tmp = {v, it->dis + w};
mp[make_pair(u, v)] = it->dis + w;
node[u].erase(it++);
node[u].insert(tmp);
}
/*for(auto it = node[u].begin(); it != node[u].end(); it++)
{
if(it->to == v)
{
cout << "Cor" << endl;
NODE tmp = {v, it->val + w};
node[u].erase(it++);
node[u].insert(tmp);
flag = false;
break;
}
}
if(flag)
{
cout << "New" << endl;
NODE tmp = {v, w};
node[u].insert(tmp);
}*/
}
if(is_iso(u)) iso_cnt++;
if(is_pat(u)) pat_cnt++;
return;
}
int main()
{
n = read(), m = read();
iso_cnt = n;
for(int k = 1;k <= m;k++)
{
for(auto it = edge[k].begin(); it != edge[k].end(); it++)
{
Upd(it->from, it->to, -it->dis);
Upd(it->to, it->from, -it->dis);
}
int num = read();
for(int i = 1; i <= num; i++)
{
int u = read(), v = read(), x = read(), y = read();
if(k + y <= m)
edge[k + y].push_back({u, v, x});
Upd(u, v, x);
Upd(v, u, x);
/*for(auto it = node[u].begin();it != node[u].end();it++)
cout << "Deb: " << u << " " << it->to << " " << it->val << endl;*/
}
num = read();
for(int i = 1; i <= num; i++)
{
int u = read();
if(is_iso(u)) cout << 0 << endl;
else
{
cout << node[u].begin()->to << endl;
}
}
int opt1 = read(), opt2 = read();
if(opt1) cout << iso_cnt << endl;
if(opt2) cout << pat_cnt << endl;
}
return 0;
}
原文地址：http://www.cnblogs.com/kevin-chance/p/16861550.html
