（时隔多日回归刷题日常...果然还是刷题最快乐）
P1111 修复公路
按时间sort一遍，每次合并两个节点，显然如果原先不连通那么合并之后联通块数量--。然后如果n==1就输出当前时间return。
#include<bits/stdc++.h> #define For(i,l,r) for(int i=l;i<=r;i++) using namespace std; const int M=2e5+5; struct node{ int x,y,t; }e[M]; int fa[M],n,m; inline int cmp(const node x,const node y){return x.t<y.t;} inline int getfa(int x){return fa[x]==x?x:getfa(fa[x]);} inline int read(){ int f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } int main(){ n=read(),m=read(); For(i,1,m) e[i].x=read(),e[i].y=read(),e[i].t=read(); sort(e+1,e+m+1,cmp); For(i,1,n) fa[i]=i; For(i,1,m){ int fx=getfa(e[i].x),fy=getfa(e[i].y); if(fx!=fy) fa[fx]=fy,n--; if(n==1) {printf("%d ",e[i].t);return 0;} } printf("-1 "); return 0; }
P2024 [NOI2001]食物链
巨简单的思路果然一交就挂，20分，但不知道错在哪里。
看了题解，学了带权并查集，一知半解吧，再去看几道题。
f[x]意义不变，re[x]记录关系AKA权值，没搞懂怎么推出来的。
我懂了，带权并查集真好。
#include<bits/stdc++.h> #define For(i,l,r) for(int i=l;i<=r;i++) using namespace std; const int M=1e5+5; int f[M],re[M]; int n,m,k,x,y,ans; int getfa(int a){ int fa=f[a]; if(a!=fa){ f[a]=getfa(fa); re[a]=(re[a]+re[fa])%3; return f[a]; } else return fa; } int main(){ cin>>n>>m; For(i,1,n) f[i]=i; while(m--){ cin>>k>>x>>y; if(x>n||y>n||(k==2&&x==y)){ans++;continue;} if(k==1){ int fx=getfa(x),fy=getfa(y); if(fx==fy&&re[x]!=re[y]){ans++;continue;} else if(fx!=fy){f[fx]=fy;re[fx]=(re[y]-re[x]+3)%3;} } if(k==2){ int fx=getfa(x),fy=getfa(y); if(fx==fy){ int rela=(re[x]-re[y]+3)%3; if(rela!=1){ans++;continue;} } else f[fx]=fy,re[fx]=(re[y]-re[x]+4)%3; } } cout<<ans<<endl; return 0; }
P1197 [JSOI2008]星球大战
一眼看过去完全没思路（也不是就是有的思路绝对T）。
结果题解告诉我 逆向思维 #做道题学个思路/算法
详细解释看代码，不是很难打，难在想，
#include<bits/stdc++.h> #define ri register int #define For(i,l,r) for(ri i=l;i<=r;i++) #define Dfor(i,r,l) for(ri i=r;i>=l;i--) using namespace std; const int M=4e5+5; int n,m,k,head[M],tot,a[M],ans[M],f[M]; bool bm[M]; struct node{ int from,to,nxt; }e[M]; inline void add(int u,int v){ e[++tot].from=u; e[tot].nxt=head[u]; e[tot].to=v; head[u]=tot; } inline int getfa(int x){ if(f[x]==x)return x; return f[x]=getfa(f[x]); } inline void hb(int u,int v){ int fu=getfa(u),fv=getfa(v); if(fu!=fv) f[fv]=fu; } int main(){ cin>>n>>m; For(i,0,n) f[i]=i; For(i,1,m){int x,y;cin>>x>>y;add(x,y),add(y,x);} cin>>k; For(i,1,k){cin>>a[i];bm[a[i]]=1;}//bm标记城市已被砸 int total=n-k;//初始化所有城市都单独存在 For(i,1,m<<1){//2*m条边 if(!bm[e[i].from]&&!bm[e[i].to]&&getfa(e[i].from)!=getfa(e[i].to)){total--;hb(e[i].from,e[i].to);} }//起点和终点都没被砸坏且两点不连通，连一条边，联通块-- ans[k+1]=total;//最后一次破坏后的个数 Dfor(i,k,1){//倒着枚举 total++;bm[a[i]]=0;//修复一个点联通块++ for(int j=head[a[i]];j;j=e[j].nxt){//枚举每一个子点 if(!bm[e[j].to]&&getfa(a[i])!=getfa(e[j].to)){total--;hb(a[i],e[j].to);} }//子点没被炸且两点不在同一个联通块，连一条边减一个联通块 ans[i]=total;//记录当前连通块数量 } For(i,1,k+1){cout<<ans[i]<<endl;} return 0; }