P1525 [NOIP2010 提高组] 关押罪犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意:
思路:
要使冲突事件的影响力最小,这里可以用贪心,让影响力大的两个尽量分开即可
那么这里可以把这么多关系按影响力从大到小排序,然后依次把已经连边的点拆开,直到发现矛盾了不能拆为止
然后问题就变成:我们怎么去“拆”,即如何去维护两个事物的对立关系
这里就要用到种类并查集了,又称扩展域并查集,用来维护两个事物的对立关系
我们先去按影响力排序,然后去遍历
如果碰到的两个结点祖先不同,即自己指向自己或已经属于不同的监狱了,那么就用种类并查集把他们分开即可
如果祖先相同,说明已经属于同一个监狱了,碰到了矛盾,那么停止“拆分”操作,止步于此,最大的边权就是改值
Code:
- #include
- using namespace std;
- const int mxn=2e4+10,mxe=1e5+10;
- #define int long long
- int n,m;
- int f[mxn<<1];
- struct ty{
- int x,y,w;
- }a[mxe];
- bool cmp(ty x,ty y){
- return x.w>y.w;
- }
- int find(int x){
- return x==f[x]?x:(f[x]=find(f[x]));
- }
- void join(int u,int v){
- int f1=find(u),f2=find(v);
- if(f1!=f2) f[f1]=f2;
- }
- void init(){
- for(int i=0;i<=n<<1;i++) f[i]=i;
- }
- signed main(){
- scanf("%lld%lld",&n,&m);
- init();
- for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].w);
- sort(a+1,a+1+m,cmp);
- for(int i=1;i<=m;i++){
- if(find(a[i].x)==find(a[i].y)){
- printf("%lld\n",a[i].w);
- return 0;
- }else{
- join(a[i].x,a[i].y+n);
- join(a[i].y,a[i].x+n);
- }
- }
- puts("0");
- return 0;
- }
总结:
思维:
1.首先是贪心的思路,求最值就考虑贪心
算法:
参考:(123条消息) P1525 [NOIP2010 提高组] 关押罪犯_bell041030的博客-CSDN博客
讲的非常好
什么时候使用种类并查集:
维护两样事物的对立关系的时候
当出现“两个集合”这种字眼的时候,就可以考虑种类并查集了
写法:
1.初始化f数组,注意原域和扩展域都要初始化
2.确定对立关系的写法:
join(a,b+n)
join(b,a+n)