历届试题PREV22---国王的烦恼

「爱情、让人受尽委屈。」 2022-01-30 14:57 252阅读 0赞

历届试题 国王的烦恼  
时间限制：1.0s 内存限制：256.0MB

问题描述  
　　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

思路：

*  差并集逆向思维：[https://blog.csdn.net/niushuai666/article/details/6662911][https_blog.csdn.net_niushuai666_article_details_6662911]
 *  每次有桥消失时，判断是否还在集团内，若不在则反抗
 *  反向思维，从零开始构造的化，若中间添加结点a,b前，判断得出a,b的根同，即添加这条路径前后都在集团内–》等同于去除这条路径前后仍在集团内部—》不反抗
 *  同理若添加a,b结点前根不同，添加后同—》去除这条路径后不在集团内–》反抗
 *  由于时间上会重合，在同一天可能会去除几条路径，所以需添加变量判断
 *  逆向思维–》所以时间需按从大到小排序

#include<bits/stdc++.h>
    using namespace std;
    struct node{
    	int a,b,k;
    }s[100001];
    int pre[100001];
    
    bool compare(node a,node b)//从大到小排序 
    {
    	return a.k>b.k;
    }
    
    int find(int root) //查找茶饼及更节电 
    {
    	int l=root;
    	if(l==pre[l]) return l;//==不是=，话说系统为什么不报错！！！ 
    	while(l!=pre[l])
    	{
    		l=pre[l];
    	}
    	pre[root]=l;
    	return l;
    }
    
    int MU(int x,int y) //制造茶饼及 
    {
    	int xx,yy;
    	xx=find(x);
    	yy=find(y);
    	if(xx==yy) return 1;//1表示之前已联 
    	else{
    		pre[xx]=yy;//不能写成pre[x]=yy;意义不一样哦
    		//本来是按树形层层递进，最高点相向才对 
    		return 0;
    	}	
    }
    
    int main()
    {
    	int n,m,t;
    	cin>>n>>m;
    	for(int i=1;i<=m;i++)
    	{
    		cin>>s[i].a>>s[i].b>>s[i].k;
    	}
    	sort(s+1,s+m,compare);
    	for(int i=1;i<=n;i++)
    	{
    		pre[i]=i;
    	}
    	int su=0,tim=-1;//su统计，ti'm表示上回时间 
    	for(int i=1;i<=m;i++)
    	{
    		if(MU(s[i].a,s[i].b)==1) continue;
    		else{
    			if(tim!=s[i].k)
    			{
    				su++;
    				tim=s[i].k;
    			}
    		}	
    	} 
    	cout<<su;
    	return 0;
    }

![在这里插入图片描述][20190519210655664.png]  
不知道为啥错了，差10分

[https_blog.csdn.net_niushuai666_article_details_6662911]: https://blog.csdn.net/niushuai666/article/details/6662911
[20190519210655664.png]: /images/20220130/13730fff73f241a2bda8fa3e10e9ee4b.png