给每条边的权值赋为编号 那么就相当于一个做kruskal的过程 也就是一个最小生成树的过程 跟BZOJ 2001 [Hnoi2010]City 城市建设一样？ 被阿爷教导了 多年前的模板又臭又长
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; typedef pair<int,int> abcd; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; } return *p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int oo=1<<30; const int N=200005; int n,m; struct edge{ int u,v,w,pos; bool operator < (const edge &B) const{ return w<B.w; } }e[25][N],d[N],t[N]; int c[N]; int a[N]; int fat[N],rnk[N]; inline void init(edge *d,int n){ for (int i=1;i<=n;i++) fat[d[i].u]=d[i].u,fat[d[i].v]=d[i].v,rnk[d[i].u]=rnk[d[i].v]=0; } inline int Fat(int u){ return u==fat[u]?u:fat[u]=Fat(fat[u]); } inline bool Union(int x,int y){ x=Fat(x),y=Fat(y); if (x==y) return 0; if (rnk[x]>rnk[y]) swap(x,y); if (rnk[x]==rnk[y]) rnk[y]++; fat[x]=y; return 1; } abcd q[N]; int Q; int ans[N]; inline int contraction(int &eds){ int tmp=0; int tsum=0; init(d,eds); sort(d+1,d+eds+1); for (int i=1;i<=eds;i++) if (Union(d[i].u,d[i].v)) t[++tmp]=d[i]; init(d,eds); for (int i=1;i<=tmp;i++) if (t[i].w!=-oo && Union(t[i].u,t[i].v)) tsum=max(tsum,t[i].w); tmp=0; for (int i=1;i<=eds;i++) if (Fat(d[i].u)!=Fat(d[i].v)){ t[++tmp]=d[i]; t[tmp].u=Fat(t[tmp].u); t[tmp].v=Fat(t[tmp].v); c[t[tmp].pos]=tmp; } for (int i=1;i<=tmp;i++) d[i]=t[i]; eds=tmp; return tsum; } inline void reduce(int &eds){ int tmp=0; init(d,eds); sort(d+1,d+eds+1); for (int i=1;i<=eds;i++) if (Union(d[i].u,d[i].v) || d[i].w==oo){ t[++tmp]=d[i]; c[t[tmp].pos]=tmp; } for (int i=1;i<=tmp;i++) d[i]=t[i]; eds=tmp; } void Solve(int l,int r,int cur,int eds,int sum){ if (l==r) a[q[l].first]=q[l].second; for (int i=1;i<=eds;i++) e[cur][i].w=a[e[cur][i].pos],d[i]=e[cur][i],c[d[i].pos]=i; if (l==r){ if (~l&1){ ans[l>>1]=sum; init(d,eds); sort(d+1,d+eds+1); for (int i=1;i<=eds;i++) if (Union(d[i].u,d[i].v)) ans[l>>1]=max(ans[l>>1],d[i].w); } return; } for (int i=l;i<=r;i++) d[c[q[i].first]].w=oo; reduce(eds); for (int i=l;i<=r;i++) d[c[q[i].first]].w=-oo; sum=max(contraction(eds),sum); for (int i=1;i<=eds;i++) e[cur+1][i]=d[i]; int mid=(l+r)>>1; Solve(l,mid,cur+1,eds,sum); Solve(mid+1,r,cur+1,eds,sum); } int idx[N]; int main(){ int T; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(T); while (T--){ read(n); read(m); read(Q); for (int i=1;i<=m;i++) read(e[0][i].u),read(e[0][i].v),e[0][i].w=i,a[i]=e[0][i].w,e[0][i].pos=i; int c=0; for (int i=1;i<=m;i++) idx[i]=i; for (int i=1;i<=Q;i++){ int x,y; read(x); read(y); q[++c]=abcd(idx[y],x),q[++c]=abcd(idx[x],y); swap(idx[x],idx[y]); } Q=c; Solve(1,Q,0,m,0); for (int i=1;i<=Q/2;i++) printf("%d\n",ans[i]); } return 0; }