蓝桥杯--- 历届试题 国王的烦恼 (并查集)

时间:2022-09-09 21:21:38
提交网址:http://lx.lanqiao.org/problem.page?gpid=T114

问题描述
  C国由n个小岛组成,为了方便小岛之间联络,C国在小岛间建立了m座大桥,每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而,由于海水冲刷,有一些大桥面临着不能使用的危险。

  如果两个小岛间的所有大桥都不能使用,则这两座小岛就不能直接到达了。然而,只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达,他们就会安然无事。但是,如果前一天两个小岛之间还有方法可以到达,后一天却不能到达了,居民们就会一起*。

  现在C国的国王已经知道了每座桥能使用的天数,超过这个天数就不能使用了。现在他想知道居民们会有多少天进行*。
输入格式   输入的第一行包含两个整数n, m,分别表示小岛的个数和桥的数量。
  接下来m行,每行三个整数a, b, t,分别表示该座桥连接a号和b号两个小岛,能使用t天。小岛的编号从1开始递增。
输出格式   输出一个整数,表示居民们会*的天数。 样例输入 4 4
1 2 2
1 3 2
2 3 1
3 4 3
样例输出 2 样例说明   第一天后2和3之间的桥不能使用,不影响。
  第二天后1和2之间,以及1和3之间的桥不能使用,居民们会*。
  第三天后3和4之间的桥不能使用,居民们会*。
数据规模和约定   对于30%的数据,1<=n<=20,1<=m<=100;
  对于50%的数据,1<=n<=500,1<=m<=10000;
  对于100%的数据,1<=n<=10000,1<=m<=100000,1<=a, b<=n, 1<=t<=100000。

题目解析:
开始的时候还SB的认为是只有一个岛屿全部的桥废掉才会*,然后排序,查找,果断WR(竟然还对了30%,醉了蓝桥杯--- 历届试题 国王的烦恼 (并查集)),其实是在出现新的连通分支的时候就要是*的一天了。。。

喜欢贴上曾经错误的代码,至少可以留一点屌丝的回忆不是么。。。
错误代码:
#include<iostream>
#include<string>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int island[10005],leftisland;//剩下的岛屿
struct Br{
int x1,x2,day;
}bri[100005];
bool cmp(Br a,Br b){
return a.day<b.day;
}
int main(){
int n,m;
int day = 1,leftbri,count=1,fightday=0;//计天数 剩下的桥梁 桥梁计数 *天数
memset(island,0,sizeof(island));

cin>>n>>m;
leftbri = m;
for(int i=1;i<=m;i++){
cin>>bri[i].x1>>bri[i].x2>>bri[i].day;
island[ bri[i].x1 ]++,island[ bri[i].x2 ]++;
}
sort(bri+1,bri+m+1,cmp);

while(leftbri>0){
int mark=1;
if(bri[count].day==day)
while(leftbri>0&&bri[count].day==day){
island[ bri[count].x1 ]--,island[ bri[count].x2 ]--;
if( mark==1&&day!=1&&island[ bri[count].x1 ]==0) fightday++,mark=0;
if( mark==1&&day!=1&&island[ bri[count].x2 ]==0) fightday++,mark=0;
count++;
leftbri--;

}
day++;
}
cout<<fightday<<endl;
return 0;
}


题目最终转化为了求连通分支的数目,但是因为随这时间是要不断查找的,如果出现了一次时间就查找一次的话,并查集好像没有这么强大,并且时间也是不允许的,所以我们巧妙的转化一下,转化为按照时间的从后向前的顺序重新建一遍树,这样相当于逆向的把树重新建了一遍,成功的在一次遍历的时候就完成了建树过程,逆向完成。。。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3
using namespace std;
int n,m;
int father[10005];
struct edge{
int u,v,c;
}e[100005];
int findf(int x){
return father[x]<0 ? x : father[x]=findf(father[x]);
}
bool cmp(edge a,edge b){
return a.c>b.c;
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++)
cin>>e[i].u>>e[i].v>>e[i].c;//分别输入的是根节点和子节点
sort(e,e+m,cmp);//按照维持天数从大到小排序
memset(father,-1,sizeof(father));
// cout<<endl<<endl;
// for(int i=0;i<m;i++)
// cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].c<<endl;
int sum=0,time=-1 ;
for(int i=0;i<m;i++){
int xx=findf(e[i].u),yy=findf(e[i].v);
if(xx!=yy){
father[xx]=yy;
if(time!=e[i].c){
time=e[i].c;
sum++;
}
}
}
cout<<sum<<endl;
return 0;
}
一直不太习惯写Union函数,但是好像写了之后变得特别清晰,以后还是要这样多多联系写Union函数
贴一下网友比较偏亮的代码:
#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 10000+5
#define maxm 100000+5
using namespace std;
int f[maxn],lastday;
struct node
{
int x, y, v;
} N[maxm];

bool cmp (node a,node b){
return a.v>b.v;
}

int Find(int x){ //找 x 所在的树根
return f[x]==x?x:f[x]=Find(f[x]);
}

bool Union(int x, int y){
int tx=Find(x),ty=Find(y);
if(tx==ty) return false; //它俩在同一个连通分量
f[tx]=ty; //合并两个连通分量
return true;
}
int main(){
int n, m;
while(~scanf("%d%d",&n,&m)) {
for(int i=0;i<m;i++)
scanf("%d%d%d",&N[i].x,&N[i].y,&N[i].v);
sort(N,N+m,cmp);
for(int i=0;i<=n;i++)
f[i]=i; //初始化并查集
int cnt=0;
lastday=-1;
for(int i=0;i<m;i++) {
if(Union(N[i].x,N[i].y) && N[i].v!=lastday){ //两个小岛不连通,且与上一个大桥的天数不同
cnt++;
lastday=N[i].v;
}
}
printf("%d\n", cnt);
}
return 0;
}

下面再做一下小总结:
关于并查集在树的连通性上发挥着巨大的作用,能够在查的同时实现和并,简化时间复杂度,另外深刻的认识到并查集远不止用来建树的,完全可以向这道题一样把拆树想象成逆向的建树,这样就完成了转化,照样可是实现问题的完美解决。
另外最近发现以下感觉和以前做过的类型相似的,但是好像又不一样,这样的话不知道怎么入手,那么就可以逆向思维,或许就会柳暗花明了。。。