NC20082. [HNOI2010]CITY 城市建设
描述
输入描述
文件第一行包含三个整数N,M,Q，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。接下来M行，第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1 ≤ Xi,Yi ≤ n, 0 ≤ Zi ≤ 50000000)，表示在城市Xi与城市Yi之间修建道路的代价为Zi。接下来Q行，每行包含两个数k,d，表示输入的第k个道路的修建代价修改为d(即将Zk修改为d)。
输出描述
输出包含Q行，第i行输出得知前i条消息后使城市连通的最小花费总和。
示例1
输入:
5 5 3 1 2 1 2 3 2 3 4 3 4 5 4 5 1 5 1 6 1 1 5 3
输出:
14 10 9
C++14(g++5.4) 解法, 执行用时: 448ms, 内存消耗: 9308K, 提交时间: 2019-08-07 09:26:10
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
return res*f;
}
#define ll long long
#define inf 1ll<<50
#define N 100005
int n,m,q,a[N],sum[50];
int f[N],c[N];ll ans[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
struct node{int x,y;}p[N];
struct edge{int x,y,pos;ll c;}t[N],e[50][N],d[N];
bool operator < (edge a,edge b){return a.c<b.c;}
void clear(int x){
for(int i=1;i<=x;i++)
f[d[i].x]=d[i].x,
f[d[i].y]=d[i].y;
}
void contraction(int &tot,ll &adt){
int tmp=0;
sort(d+1,d+1+tot);clear(tot);
for(int i=1;i<=tot;i++){
int fx=find(d[i].x),fy=find(d[i].y);
if(fx==fy)continue;
f[fx]=fy,t[++tmp]=d[i];
}
for(int i=1;i<=tmp;i++) f[t[i].x]=t[i].x,f[t[i].y]=t[i].y;
for(int i=1;i<=tmp;i++){
if(t[i].c==-inf)continue;
int fx=find(t[i].x),fy=find(t[i].y);
adt+=t[i].c,f[fx]=fy;
}tmp=0;
for(int i=1;i<=tot;i++){
int fx=find(d[i].x),fy=find(d[i].y);
if(fx==fy)continue;
t[++tmp]=d[i];
t[tmp].x=find(d[i].x);
t[tmp].y=find(d[i].y);
c[d[i].pos]=tmp;
}tot=tmp;
for(int i=1;i<=tot;i++)d[i]=t[i];
}
void reduction(int &tot){
sort(d+1,d+1+tot);
clear(tot);int tmp=0;
for(int i=1;i<=tot;i++){
int fx=find(d[i].x),fy=find(d[i].y);
if(fx==fy){
if(d[i].c==inf) t[++tmp]=d[i],c[d[i].pos]=tmp;
continue;
}f[fx]=fy;
t[++tmp]=d[i],c[d[i].pos]=tmp;
}tot=tmp;
for(int i=1;i<=tot;i++)d[i]=t[i];
}
void solve(int l,int r,int now,ll adt){
int tot=sum[now];
if(l==r)a[p[l].x]=p[l].y;
for(int j=1;j<=tot;j++)
e[now][j].c=a[e[now][j].pos],d[j]=e[now][j],c[e[now][j].pos]=j;
if(l==r){
clear(tot);
sort(d+1,d+1+tot);
for(int j=1;j<=tot;j++){
int fx=find(d[j].x),fy=find(d[j].y);
if(fx==fy)continue;
f[fx]=fy;adt+=d[j].c;
}ans[l]=adt;
return ;
}int mid=(l+r)>>1;
for(int i=l;i<=r;i++)d[c[p[i].x]].c=-inf;
contraction(tot,adt);
for(int i=l;i<=r;i++)d[c[p[i].x]].c=inf;
reduction(tot);
sum[now+1]=tot;
for(int i=1;i<=tot;i++)e[now+1][i]=d[i];
solve(l,mid,now+1,adt);
solve(mid+1,r,now+1,adt);
}
int main(){
n=read(),m=read(),q=read();
for(int i=1;i<=m;i++){
e[0][i].x=read(),e[0][i].y=read();
e[0][i].pos=i,a[i]=e[0][i].c=read();
}sum[0]=m;
for(int i=1;i<=q;i++) p[i].x=read(),p[i].y=read();
solve(1,q,0,0);
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
}
C++11(clang++ 3.9) 解法, 执行用时: 482ms, 内存消耗: 16976K, 提交时间: 2019-03-16 10:42:52
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define inf 50000001
#define N 20010
#define M 50010
#define LL long long
char B[1<<15],*cS=B,*cT=B;
#define getc (cS==cT&&(cT=(cS=B)+fread(B,1,1<<15,stdin),cS==cT)?0:*cS++)
inline int read()
{
int x=0;register char c=getc;
while(c<'0'||c>'9')c=getc;
while(c>='0'&&c<='9')x=10*x+(c^48),c=getc;
return x;
}
int n,m,q;
struct edge{int st,ed,val,L,R;}s[M];
vector<edge>E;
struct Gragh
{
int fa[N];
inline int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);}
inline void intn(int sz){for(int i=1;i<=sz;++i)fa[i]=i;}
}S;
inline bool mt(const edge &a,const edge &b){return a.val<b.val;}
LL ans[M];
int sta[M<<1],stb[M<<1],stc[M<<1];
int id[N];
inline void CDQ(int l,int r,int size,vector<edge> Ex)
{
vector<edge> tmp;
int i,sz,x,y,cnt,mi=l+r>>1;edge z;
for(i=0,sz=Ex.size();i<sz;++i)
if(l<=Ex[i].R&&Ex[i].L<=r)tmp.push_back(Ex[i]);
sort(tmp.begin(),tmp.end(),mt);
S.intn(size);LL temp=0;
for(i=0,sz=tmp.size();i<sz;++i)
{
z=tmp[i],stc[i]=(z.L<=l&&r<=z.R),
sta[i]=stb[i]=0,x=S.find(z.st),y=S.find(z.ed);
if(x!=y)
{
S.fa[x]=y;
if(stc[i])temp+=z.val,sta[i]=1;
}
}
for(i=l;i<=r;++i)ans[i]+=temp;
if(l==r)return;
S.intn(size);
for(i=0,sz=tmp.size();i<sz;++i)
{
z=tmp[i],x=S.find(z.st),y=S.find(z.ed);
if(x==y)stb[i]=1;
else if(stc[i])S.fa[x]=y;
}
S.intn(size);
for(i=0,sz=tmp.size();i<sz;++i)
if(sta[i]){z=tmp[i],S.fa[S.find(z.st)]=S.find(z.ed);}
for(cnt=0,i=1;i<=size;++i)
if(S.find(i)==i)id[i]=++cnt;
Ex.clear();
for(i=0,sz=tmp.size();i<sz;++i)
if(!sta[i]&&!stb[i])
tmp[i].st=id[S.find(tmp[i].st)],
tmp[i].ed=id[S.find(tmp[i].ed)],
Ex.push_back(tmp[i]);
CDQ(l,mi,cnt,Ex);
CDQ(mi+1,r,cnt,Ex);
}
int last[M];
int main()
{
register int i,j,x,y;edge z;
n=read(),m=read(),q=read();
for(i=1;i<=m;++i)
s[i].st=read(),s[i].ed=read(),s[i].val=read();
for(i=1;i<=q;++i)
x=read(),y=read(),z=s[x],z.L=last[x],z.R=i-1,
E.push_back(z),s[x].val=y,last[x]=i;
for(i=1;i<=m;++i)
s[i].L=last[i],s[i].R=q,E.push_back(s[i]);
CDQ(1,q,n,E);
for(i=1;i<=q;++i)
printf("%lld\n",ans[i]);
}