[HNOI 2010] 城市建设
\(\mathbb{Description}\)
\(\rm Link.\)
\(\mathbb{Solution}\)
感觉好 \(\rm nb\) 但是这辈子可能不会用到的分治做法
这个标题真的好长长长长长长长长长长长长长长长长长长。另外插一句闲话,这题应该是保证了 \(m\) 条边一定连通吧……
首先考虑线段树分治。但是 \(\rm kruskal\) 无法无序插入,只能支持边权从小到大插入。我们考虑,将分治区间 \([l,r]\) 的有用边数减少至 \(\mathcal O(r-l)\) 级别,这样每个区间求一次 \(\rm kruskal\) 也是 \(\mathcal O(n\log^2 n)\) 的。考虑对于区间 \([l,r]\),令 \([l,r]\) 中修改的边为 "动态边",反之为 "静态边",分别用 \(E,E'\) 来表示,涉及的点集就是 \(V\).
- 将 \(E\) 中的边全都赋值为 \(-\infty\)。此时在 \(G(V,E\cup E')\) 上跑 \(\rm kruskal\),那么如果有静态边 \(e\) 被选入最小生成树,在之后递归的 子区间 内,这条静态边一定也会被选入最小生成树。证明可以这样考虑:\(e\) 一定连接两个连通块,且是连接这两个连通块的最小权(显然连通块之间不存在动态边)。除此之外,我们可以删去在必选静态边基础上失去作用的静态边。那么就只剩下必选静态边、动态边、可能有用的静态边。由于必选静态边已经必选,所以我们利用这些边进行缩点,将边权加入答案,并删除这些边。
- 将 \(E\) 中的边全都赋值为 \(+\infty\)。注意这是在上个操作的基础之上再跑 \(\rm kruskal\),此时如果有静态边不在最小生成树中,那么之后也一定不在最小生成树中,所以删去这些边。现在只剩下动态边、在最小生成树上的静态边。可以发现,我们成功将边数缩减到动态边的级别。另外可以发现的是,实际上是 \([l,\text{mid}]\) 这个区间边数大约为 \(r-l\).
\(\rm lct\)
从 "\(\text{[NOI 2014] }\)魔法森林" 一题中学到了动态维护最小生成树的 \(\rm trick\),对于此题,由于 \(\rm lct\) 不能支持边权修改(这是因为我们的维护基于贪心的思想),所以再套一个线段树分治就好啦~
代码实现先咕着吧,如果写不来今天模拟赛就滚回来写。
\(\mathbb{Code}\)
# include
# include
# define print(x,y) write(x), putchar(y)
template
inline T read(const T sample) {
T x=0; bool f=0; char s;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp]=x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}
# include
using namespace std;
typedef long long ll;
const int infty = 1e9;
const int maxn = 5e4+5;
ll ans[maxn],val[maxn];
int n,m,q,f[maxn],tp,siz[20],ref[maxn];
struct query { int id,w; } p[maxn];
struct edge {
int u,v,w,id;
bool operator < (const edge& t) const { return w>1, cnt=siz[d];
for(int i=1;i<=cnt;++i)
e[d][i].w=val[e[d][i].id],
t[i]=e[d][i], ref[t[i].id]=i;
if(l==r) {
initialize(cnt);
for(int i=1;i<=cnt;++i) if(fin(t[i].u)^fin(t[i].v))
f[fin(t[i].u)]=fin(t[i].v), cur += t[i].w;
ans[l]=cur;
return;
}
for(int i=l;i<=r;++i) t[ref[p[i].id]].w = -infty; delEdge(cnt,cur);
for(int i=l;i<=r;++i) t[ref[p[i].id]].w = infty; _delEdge(cnt);
siz[d+1] = cnt;
for(int i=1;i<=cnt;++i) e[d+1][i]=t[i];
dicon(l,mid,d+1,cur); dicon(mid+1,r,d+1,cur);
}
int main() {
n=read(9), m=read(9), q=read(9); siz[0]=m;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1;i<=m;++i) {
e[0][i].id=i;
e[0][i].u=read(9), e[0][i].v=read(9), val[i]=e[0][i].w=read(9);
}
for(int i=1;i<=q;++i) p[i].id=read(9), p[i].w=read(9);
dicon(1,q,0,0);
for(int i=1;i<=q;++i) print(ans[i],'\n');
return 0;
}