【BZOJ2001】 [Hnoi2010]City 城市建设
2024-10-15 01:55:34
BZOJ2001 [Hnoi2010]City 城市建设
Solution
我们考虑一下这个东西怎么求解?
思考无果......
咦?
好像可以离线cdq,每一次判断一下如果这条边如果不选就直接删除,然后不确定的保留,必须选的就去确定连通性.
然后可以了?
好妙啊.cdq果然还是万金油.
代码实现
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
int f=1,sum=0;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
const int N=100010,Inf=1e9+10;
struct node{
int u,v,w,id;
bool operator<(const node b)const{
return w<b.w;
}
}E[N],e[60][N],tmp[N],st[N];
int f[N],c[N],siz[50],W[N];
ll ans[N];
struct ques{
int w,x;
}q[N];
int find(int x){
if(x!=f[x])f[x]=find(f[x]);
return f[x];
}
void init(int z){
for(int i=1;i<=z;i++)f[tmp[i].u]=tmp[i].u;
for(int i=1;i<=z;i++)f[tmp[i].v]=tmp[i].v;
}
void Solve1(int &z,ll &Ans){
init(z);sort(tmp+1,tmp+z+1);int top=0;
for(int i=1;i<=z;i++)
if(find(tmp[i].u)!=find(tmp[i].v)){
f[find(tmp[i].u)]=find(tmp[i].v);
st[++top]=tmp[i];
}
for(int i=1;i<=top;i++)f[st[i].u]=st[i].u,f[st[i].v]=st[i].v;
for(int i=1;i<=top;i++)
if(st[i].w>-Inf){
f[find(st[i].u)]=find(st[i].v);
Ans+=st[i].w;
}
top=0;
for(int i=1;i<=z;i++)
if(find(tmp[i].u)!=find(tmp[i].v)){
st[++top]=tmp[i];
c[tmp[i].id]=top;
st[top].u=find(tmp[i].u);
st[top].v=find(tmp[i].v);
}
z=top;for(int i=1;i<=top;i++)tmp[i]=st[i];
}
void Solve2(int &z)
{
init(z);sort(&tmp[1],&tmp[z+1]);int top=0;
for(int i=1;i<=z;++i)
if(find(tmp[i].u)!=find(tmp[i].v))
f[find(tmp[i].u)]=find(tmp[i].v),st[++top]=tmp[i],c[tmp[i].id]=top;
else if(tmp[i].w>=Inf)st[++top]=tmp[i],c[tmp[i].id]=top;
z=top;for(int i=1;i<=top;++i)tmp[i]=st[i];
}
void cdq(int l,int r,int dep,ll Ans){
if(l==r)W[q[l].x]=q[l].w;
int z=siz[dep],mid=(l+r)>>1;
for(int i=1;i<=z;i++)e[dep][i].w=W[e[dep][i].id];
for(int i=1;i<=z;i++)tmp[i]=e[dep][i],c[tmp[i].id]=i;
if(l==r){
init(z);sort(tmp+1,tmp+z+1);
for(int i=1;i<=z;i++)
if(find(tmp[i].u)!=find(tmp[i].v)){
f[find(tmp[i].u)]=find(tmp[i].v);Ans+=tmp[i].w;
}
ans[l]=Ans;return;
}
for(int i=l;i<=r;i++)tmp[c[q[i].x]].w=-Inf;
Solve1(z,Ans);
for(int i=l;i<=r;i++)tmp[c[q[i].x]].w=+Inf;
Solve2(z);
for(int i=1;i<=z;i++)e[dep+1][i]=tmp[i];siz[dep+1]=z;
cdq(l,mid,dep+1,Ans);cdq(mid+1,r,dep+1,Ans);
}
int main()
{
int n,m,Q;
n=gi();m=gi();Q=gi();
for(int i=1;i<=m;i++)E[i].u=gi(),E[i].v=gi(),E[i].w=gi(),E[i].id=i;
for(int i=1;i<=Q;i++)q[i].x=gi(),q[i].w=gi();
for(int i=1;i<=m;i++)W[i]=E[i].w;
for(int i=1;i<=m;i++)e[0][i]=E[i];
siz[0]=m;cdq(1,Q,0,0);
for(int i=1;i<=Q;i++)printf("%lld\n",ans[i]);
return 0;
}
最新文章
- Linux开源系统对比Windows闭源系统的优势解析
- 微信企业号开发之-如何获取secret 序列号
- Fallout4 Creation Kit
- log4net使用的关键点
- 特性节点Attribute
- 漫谈php全局变量Global
- 学习C++ Primer 的个人理解(十)
- 选择排序(C++)
- Android 网络框架---Volley
- 【又长见识了】C#异常处理,try、catch、finally、throw
- 腾讯云万象优图每个账户提供50G的图片存储(支持黄图检测)
- iOS地理围栏技术的应用
- 【转】操作系统 gdt ldt
- Cocos2D:塔防游戏制作之旅(十七)
- 【代码笔记】Web-JavaScript-JavaScript表单验证
- RelativeLayout 总结
- Spring容器IOC解析及简单实现(转)
- oracle 中从某天到某天一天一次执行某个函数
- C# 词法分析器(一)词法分析介绍
- 上白泽慧音(tarjan,图的染色)
热门文章
- New users can not log on Win8
- spring学习九 spring aop详解
- canvas 实现飞碟射击游戏
- Linux运维之Ansible自动化运维管理工具
- python之并发编程初级篇8
- GOAP
- Linux+Apache+Mysql+PHP优化技巧
- jitter
- error C2065: &#39;IDD_DIALOG1&#39; : undeclared identifier
- Mybatis-Plus 实战完整学习笔记(八)------delete测试