国王饮水记 题解(

题目传送门 step1:暴力 对于每次询问，都进行一次krusal计算。

#include<cstdio> #include<algorithm> #define maxn 5039 using namespace std; inline int read(){ char c=getchar(); int sum=0,flag=0; while((c<'0'||c>'9')&&c!='-') c=getchar(); if(c=='-') c=getchar(),flag=1; while('0'<=c&&c<='9'){ sum=(sum<<1)+(sum<<3)+(c^48); c=getchar(); } if(flag) return -sum; return sum; } struct JTZ{ int f,t,w; bool operator < (const JTZ x) const { return this->w < x.w; } }e[maxn]; int f[maxn]; int n,m; int getfa(int x){ if(x==f[x]) return x; return f[x]=getfa(f[x]); } void getans(int x){ int sum=0; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=x;i++){ if(getfa(e[i].f)!=getfa(e[i].t)){ f[getfa(e[i].f)]=getfa(e[i].t); sum+=e[i].w; } } int tmp=getfa(1),ans=0; for(int i=1;i<=n;i++) if(getfa(i)==tmp) ans++; printf("%d %d\n",sum,ans); } int main(){ //freopen("1.in","r",stdin); n=read(); m=read(); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++){ e[i].f=read(); e[i].t=read(); e[i].w=read(); sort(e+1,e+i+1); getans(i); } return 0; }

step 2:优化 将排序改为 $O\left(lo{g}_N+N\right)$ 的二分查找，但是分数怎么变少了啊

#include<cstdio> #include<algorithm> #define maxn 5039 using namespace std; inline int read(){ char c=getchar(); int sum=0,flag=0; while((c<'0'||c>'9')&&c!='-') c=getchar(); if(c=='-') c=getchar(),flag=1; while('0'<=c&&c<='9'){ sum=(sum<<1)+(sum<<3)+(c^48); c=getchar(); } if(flag) return -sum; return sum; } struct JTZ{ int f,t,w; }e[maxn]; int f[maxn]; int n,m; int getfa(int x){ if(x==f[x]) return x; return f[x]=getfa(f[x]); } void getans(int x){ int sum=0; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=x;i++){ if(getfa(e[i].f)!=getfa(e[i].t)){ f[getfa(e[i].f)]=getfa(e[i].t); sum+=e[i].w; } } int tmp=getfa(1),ans=0; for(int i=1;i<=n;i++) if(getfa(i)==tmp) ans++; printf("%d %d\n",sum,ans); } int main(){ //freopen("1.in","r",stdin); n=read(); m=read(); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++){ e[i].f=read(); e[i].t=read(); e[i].w=read(); int l,r,mid; l=1,r=i; while(l+1<r){ mid=l+r>>1; if(e[mid].w<=e[i].w) l=mid; else r=mid; } JTZ tmp=e[i]; for(int j=i-1;j>=l+1;j--) e[j+1]=e[j]; e[l+1]=tmp; getans(i); } return 0; }

step3:未完成 将输入的一条边进行判断： 如果两点不连通，那么就连起来。 如果两条边连起来能减小生成树的边权值，那就连起来，否则就不连。 代码略。