题目

题目描述
给 $n$ 点 $m$ 边无向图。最初所有边都被 $\text{DDG}$ 看守而不能通过。但是，记 $S_i$ 为可通过的边构成的连通块中包含 $i$ 的那个，若 ${\sum }_{x\in S_u}{a}_x+{\sum }_{y\in S_v}{a}_y⩾e_{a,b}$ 且 $v\notin S_u$，则 $⟨u,v⟩$ 上可以建造黑色大桥（就不会受到 $\text{DDG}$ 的侵扰）而因此可通过了！当然 $S$ 也会对应变化。

在所有方案中，求出修建的黑色大桥总数最多的前提下，字典序最小的修建序列。

数据范围与提示
$n⩽10^5$，边权 $e_{u,v}⩽10^6$，点权 $a_i\in [0,10^6]$ 。

思路

省流：没有任何参考价值。当成结论背下来算了。

第一反应：需维护 $\mathcal{O}(\mathrm{deg})$ 的信息。启发式合并？大小点分治？都没走通。

隐晦的条件：一条边的判断条件只与两个值的变化有关。于是有了个不可能被我这等凡人想到的做法：对于每条边，设其 $\text{sum}(S_u)+\text{sum}(S_v)$ 还需 $\delta$ 的增幅。则 $\text{sum}(S_u)$ 和 $\text{sum}(S_v)$ 至少其一拥有 $\lceil \frac{\delta }{2}\rceil$ 的增幅。

因此把 $\mathrm{t}\mathrm{a}\mathrm{g}$ 打上，被触发时检查，合并连通块就启发式合并。而一条边只会被检查 $\log e$ 次，因此总复杂度 $\mathcal{O}[m\log m(\log m+\log e)]$ 或 $\mathcal{O}(m\log m\log e)$ 。

代码

#include <cstdio>
#include <algorithm> // Almighty XJX yyds!!
#include <cstring> // oracle: ZXY yydBUS!!!
#include <cctype> // Huge Egg Dog ate me!!!
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <utility>
#include <queue>
using namespace __gnu_pbds;
using llong = long long;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
	for(; isdigit(c); c=getchar()) a = a*10+(c^48);
	return a*f;
}

const int MAXN = 100000;
using PII = std::pair<int,int>;
tree<PII,null_type,std::less<PII>,splay_tree_tag> tre[MAXN];
int val[MAXN], fa[MAXN];
inline int findSet(int a){
	if(fa[a] == a) return a;
	return fa[a] = findSet(fa[a]);
}

std::priority_queue<int> todo;
int cost[MAXN<<1], ep[MAXN<<1][2];
std::queue<int> ans;
int main(){
	int n = readint(), m = readint();
	rep0(i,0,n) val[i] = readint(), fa[i] = i;
	for(int i=0,a,b; i!=m; ++i){
		a = ep[i][0] = readint()-1;
		b = ep[i][1] = readint()-1;
		cost[i] = readint();
		if(val[a]+val[b] >= cost[i]) todo.push(-i);
		else{ // half to check
			tre[a].insert(PII{(cost[i]+1+val[a]-val[b])>>1, i});
			tre[b].insert(PII{(cost[i]+1-val[a]+val[b])>>1, i});
		}
	}
	while(!todo.empty()){
		int x = -todo.top(); todo.pop();
		if(findSet(ep[x][0]) == findSet(ep[x][1])) continue;
		int faa = findSet(ep[x][0]), fab = findSet(ep[x][1]);
		if(tre[fab].size() > tre[faa].size()) tre[faa].swap(tre[fab]);
		for(const PII &v : tre[fab]) tre[faa].insert(v);
		val[faa] += val[fab], ans.push(x), fa[fab] = faa;
		while(!tre[faa].empty() && tre[faa].begin()->first <= val[faa]){
			x = tre[faa].begin()->second;
			tre[faa].erase(tre[faa].begin());
			if(findSet(ep[x][0]) == findSet(ep[x][1])) continue;
			int l = findSet(ep[x][0]), r = findSet(ep[x][1]);
			if(val[l]+val[r] >= cost[x]) todo.push(-x); // available
			else{ // still cut in half
				tre[l].insert(PII{(cost[x]+1+val[l]-val[r])>>1, x});
				tre[r].insert(PII{(cost[x]+1-val[l]+val[r])>>1, x});
			}
		}
	}
	printf("%d\n",int(ans.size()));
	for(; !ans.empty(); ans.pop())
		printf("%d ",ans.front()+1);
	putchar('\n');
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71