关押罪犯-详解-noip2010-并查集--搜索--二分图

关押罪犯 网址：https://vijos.org/p/1776

-----------

题目解析：

题意：按照样例最终分的结果是：

监狱1 ： 1 4 被关押 他们中间会爆发2534的冲突

监狱2 ：2  3被关押 他们会爆发3512冲突

这是所有冲突里面最大值最小的一个：

其他任何一种变动都会让12884 6618 28351 这3个比3512大的冲突产生，所以3512为题目所求，图中为最终分配

算法分析：

也就是说把尽量分开怒气值大的，分不下去了的怒气值就是最后的冲突值，关键怎么把这n个罪犯分到2个监狱里面

基本上第一步都是把m个怒气值从大到小排序

尝试下，解题过程

第1次分：1 2 28351 最大 

分法1：监狱1： 1 监狱2 ：2

分法2：监狱1： 2 监狱2：1

第2次分：3 4 12884 次大，问题来了，3在监狱1、4在监狱2 还是 3在监狱2、4在监狱1？？？？

分法1：监狱1： 1 3 监狱2： 2 4

分法2：监狱1 ：1 4 监狱2： 2 3

分法3：监狱1： 2 3 监狱2： 1 4

分法4：监狱1： 2 4 监狱2： 1 3

第3次分：1 3 6618

分法1： 监狱1： 1 3  1监狱2：2 4 3  监狱1里面1 3 共存，这种分法不成立

分法2： 监狱1： 1 3 3 监狱2： 2 4 1 监狱1里面1 3 共存，这种分法不成立

分法3： 监狱1： 1 4 1 监狱2： 2 3 3  满足其实就是 1 4----2 3

分法4： 监狱1： 1 4 3 监狱2： 2 3 1 监狱2里面1 3共存，这种分法不成立

分法5：监狱1：  2 3 1 监狱2： 1 4 3 等价于分法4 不成立

分法6：监狱1： 2 3 3 监狱2： 1 4 1 等价于分法3 成立

分法7：监狱1： 2 4 1 监狱2： 1 3 3 等价于分法2 不成立

分法8：监狱1： 2 4 3 监狱2： 1 3 1 等价于分法1 不成立

第4次分：2 3 3512

第3次分后只有分法3.6可以继续分，那就再找个基础上继续分：

分法1：监狱1： 1 4 1 2 监狱2： 2 3 3 3 监狱1里面jy1[1]=1 jy2[1]=2 两者不能共存，但是监狱1里面jy1[1]=1 jy1[4]=2分一起了，这种分法不成立

分法2：监狱1： 1 4 1 3 监狱2： 2 3 3 1 监狱1里面jy1[1]=1 jy2[1]=2 两者不能共存，但是监狱2里面jy2[1]=2 jy2[4]=1分一起了，这种分法不成立

分法3：略 等价于1.2

分法4：略 等价于1.2

也就是，第4次肯定不能分，2和3没有办法在2个不同监狱，必然冲突，那么他们的怒气值3512就是所求的所有可能冲突里面，最大怒气值的最小值

由此可以尝试广度搜索，第i层表示要拆分第i组怒气值对，第i层的每个节点，表示第1组怒气对,第2组怒气对,,,,第i组怒气对，在监狱1,2的一种分法如图：

因为右孩子和左孩子表示的只是 2个监狱所关押的罪犯完全互换，对最终的冲突没有影响，左右只走左子树即可，监狱1,2只是为了表述方便定义的

那紧接着分析广搜的可行性，时空复杂度，首先就是每个节点的定义：

分析1：

struct Node{

   int jy1[M];

   int jy2[M];

};

按照监狱1： 1 4 1 监狱2： 2 3 3  满足其实就是 1 4----2 3  在第3次分的时候，虽然这两者等价，但是却不能记录成 1 4 ---2 3 是因为 

每个监狱的第x_1，x_2来说，还表示了他两的拆分关系，也就是他两是不能在一个监狱的信息而1 4 ---2 3 是体现的是12,34不能在一个，灭有体现1 3 不能在一起

从这个角度上讲，有m组怒气值，那每个监狱的大小就是jy1[M]了 M为10万

在第i层会有2^i-1个节点，要是广搜扩展，会炸锅的吧？？？？？？？？？？？？？-

一个节点消耗 20*10^4*2*4(int) ~10^6~1MB——4GB的堆也就4000个节点  2^n ~4000 2^10~10^3 n~12 也就是基本第12层，第12组怒气值就可以爆了，而怒气值是10万

一共最多2万个罪犯，会走到第10万层才终止吗？

极端例子：

犯人1和其他 10万-1个犯人有怒气值

那么最终的节点结果是：

(1,1,1...1)(2,3,4...99999) 真的可以走到第10万层  但是貌似其他分支都可以被剪掉比如（1,1）（2,3） 和（1,3）（2,1）->这个明显会被剪掉---

如果采用，动态分配和释放空间的话，可以吗？？？？？

另外个例子：

1   2

3  4

99999 100000 怒气值成对分布

那么显然可以出现(1,3)(2,4) 、(1,4)(2,3)类似排列分布了，到第100000/2 = 50000个节点，肯定会超空间的吧-------------------------

所以这种表示方式下，广搜不可行，深搜呢？

/****/

骗分导论中说：
在Windows XP SP2，Dev-cpp 下测试，深度约为130000；在Redflag Linux 7.0，gcc下测试，深度约为780000

感觉如果把Node写出全局变量，深搜应该是可以的，但是广搜相对来说，如果搜索到第k层所有节点都矛盾，那么第k组就是我们要输出的，后面不用再搜索

而深搜貌似也是搜索到第k层就可以了，因为第k层的所有节点都矛盾的话，那么第k+1层肯定也矛盾，直接就返回了

---------------------------------------------------------------------

深搜真的可以吗？

每个节点，都需要判断可行性，也就是加入新怒气对后是否产生矛盾点，也就是剪枝函数

判断条件1：jy1[x] 和 jy2[x] 是一对不能在一起的，那么在监狱1加入jy1[k]之后，在1.2.3..k-1里面找是否有jy2[k]数值出现，比如

样例：（1,3）（2,4） 加入1-3一种分法是：(1,3,1)(2,4,3) jy1[3]=1 jy2[3]=3互为冲突对，在jy1[1]=1 jy1[2]=3里面出现了3这个敌对项，这种分法不成立

同样监狱2也如此判断下 

朴素的循环一遍时间复杂度为o(n) 这里是n略为10万，那10万深度*10万判断 100亿  妥妥爆时间吧？？？？？？

时间优化：在这种离散、有序、有范围的查找里，二分效率很高，那维护Jy1,jy2有序首先得破坏jy1[x] jy2[x]敌对关系，这个关系破坏也没影响，因为只需要第k对的敌对关系

1..k-1既然可以放进来，说明他们是可以的，但维护jy1,jy2有序的话时间复杂度起码也得O(n)吧？10万*10万，妥妥炸，不过说到这里，就不得不提起并查集一个特点了：

优秀的查询性能，既然只看在不在一个集合那并查集很胜任啊

-------------------------------------------------

在谈论并查集来完成查找之前，说说，深搜广搜真的就不行了吗，一个爆空间，一个爆时间

先说空间：可以改成

struct Node{

  int jy1[20001];

 int jy2[20001];

};

因为前面讨论过了监狱里面的犯人顺序并不重要，而最多20000个犯人，所以空间优化成如上，广搜还是不行，深搜试试：

就算找到一个较小的anser 也无法用来剪枝，因为层次就代表着怒气值从大到小，肯定是从高到低，这简直就是一个因为缺乏剪枝这就是暴力枚举了，时间复杂度2^n次方

而且还是在利用在监狱1的 对应位置1 jy1[1]=1 表示犯人1在监狱1 jy1[x]=1表示犯人x在监狱1，这种简化了找某个数在监狱存在否的查询

//#include <StdAfx.h>
#include <stdlib.h>//system("pause")
#include <stdio.h>
#include <string>//string
#include <iostream>
#include <cstring>//memset
#include <algorithm>//sort
using namespace std;typedef struct ChongTu{int from;int to;int anger;
} ChongTu;
typedef struct Node{int jy1[20001];int jy2[20001];
}Node;ChongTu ct[100001];
Node nd,isUsed;
int n,m,anser=1e9;void Dfs(int k)
{if (k==m+1) {cout<<0;return;}//左分支int k1 = ct[k].from;//int k2 = ct[k].to;////看k2在监狱1里面是否出现，如果已经在，那k1放监狱1，k2放监狱2不可行//或者k1在监狱2里面出现，如果已经在，那么k1放监狱1，k2放监狱2不可行if (nd.jy1[k2]==1 || nd.jy2[k1]==1) {if  (anser>ct[k].anger) {anser = ct[k].anger;}}else //可以这样放，搜索下一层{//k1本来就在监狱1里面，那么搜完这层之后k1还在监狱1//k1如果本来不在监狱1，那么将其放在监狱1搜索后，要从监狱1里面移除int oldState1 = nd.jy1[k1];int oldState2 = nd.jy2[k2];nd.jy1[k1] = 1;//置标志位，第k组第1个犯人放入监狱1nd.jy2[k2] = 1;//置标志位，第k组第2个犯人放入监狱2Dfs(k+1);//还原原状态nd.jy1[k1] = oldState1;nd.jy2[k2] = oldState2;}//看k1在监狱1里面是否出现，如果已经在，那k2放监狱1，k1放监狱2不可行//或者k2在监狱2里面出现，如果已经在，那么k2放监狱1，k1放监狱2不可行if (nd.jy1[k1]==1 || nd.jy2[k2]==1){if  (anser>ct[k].anger) {anser = ct[k].anger;}}else{//k2本来就在监狱1里面，那么搜完这层之后k2还在监狱1//k2如果本来不在监狱1，那么将其放在监狱1搜索后，要从监狱1里面移除int oldState2 = nd.jy1[k2];int oldState1 = nd.jy2[k1];nd.jy1[k2] = 1;//k2放入监狱1nd.jy2[k1] = 1;//k1放入监狱2Dfs(k+1);//释放nd.jy1[k2] = oldState2;nd.jy2[k1] = oldState1;}
}int Cmp(ChongTu x, ChongTu y)
{if (x.anger>y.anger)return 1;else return 0;
}
int main()
{int i;//读入数据cin>>n>>m;for (i=1;i<=m;i++) cin>>ct[i].from>>ct[i].to>>ct[i].anger;sort(ct+1,ct+m+1,Cmp);//for (i=1; i<=m; i++) cout<<ct[i].from<<' '<<ct[i].to<<' '<<ct[i].anger<<endl;//测试sortDfs(1);cout<<anser;//system("pause");return 0;}

后面尝试了一些情况细节的处理，比如当m>1时初始 (1)(2) 不找(2)(1)Dfs(2)开始，当M<=1直接输出0

或者加了是否找到一个0  结果依然同上

//#include <StdAfx.h>
#include <stdlib.h>//system("pause")
#include <stdio.h>
#include <string>//string
#include <iostream>
#include <cstring>//memset
#include <algorithm>//sort
using namespace std;typedef struct ChongTu{int from;int to;int anger;
} ChongTu;
typedef struct Node{int jy1[20001];int jy2[20001];
}Node;ChongTu ct[100001];
Node nd,isUsed;
int n,m,anser=1e9;
int flag = 0;void Dfs(int k)
{if (flag==1) return;if (k==m+1 ) {cout<<0;flag=1;return;}//左分支int k1 = ct[k].from;//int k2 = ct[k].to;////看k2在监狱1里面是否出现，如果已经在，那k1放监狱1，k2放监狱2不可行//或者k1在监狱2里面出现，如果已经在，那么k1放监狱1，k2放监狱2不可行if (nd.jy1[k2]==1 || nd.jy2[k1]==1) {if  (anser>ct[k].anger) {anser = ct[k].anger;}}else //可以这样放，搜索下一层{//k1本来就在监狱1里面，那么搜完这层之后k1还在监狱1//k1如果本来不在监狱1，那么将其放在监狱1搜索后，要从监狱1里面移除int oldState1 = nd.jy1[k1];int oldState2 = nd.jy2[k2];nd.jy1[k1] = 1;//置标志位，第k组第1个犯人放入监狱1nd.jy2[k2] = 1;//置标志位，第k组第2个犯人放入监狱2Dfs(k+1);//还原原状态nd.jy1[k1] = oldState1;nd.jy2[k2] = oldState2;}//看k1在监狱1里面是否出现，如果已经在，那k2放监狱1，k1放监狱2不可行//或者k2在监狱2里面出现，如果已经在，那么k2放监狱1，k1放监狱2不可行if (nd.jy1[k1]==1 || nd.jy2[k2]==1){if  (anser>ct[k].anger) {anser = ct[k].anger;}}else{//k2本来就在监狱1里面，那么搜完这层之后k2还在监狱1//k2如果本来不在监狱1，那么将其放在监狱1搜索后，要从监狱1里面移除int oldState2 = nd.jy1[k2];int oldState1 = nd.jy2[k1];nd.jy1[k2] = 1;//k2放入监狱1nd.jy2[k1] = 1;//k1放入监狱2Dfs(k+1);//释放nd.jy1[k2] = oldState2;nd.jy2[k1] = oldState1;}
}int Cmp(ChongTu x, ChongTu y)
{if (x.anger>y.anger)return 1;else return 0;
}
int main()
{int i;//读入数据cin>>n>>m;for (i=1;i<=m;i++) cin>>ct[i].from>>ct[i].to>>ct[i].anger;sort(ct+1,ct+m+1,Cmp);//for (i=1; i<=m; i++) cout<<ct[i].from<<' '<<ct[i].to<<' '<<ct[i].anger<<endl;//测试sortint k1 = ct[1].from;//int k2 = ct[1].to;//nd.jy1[k1] = 1;nd.jy2[k2] = 1;//直接初始化第一层，从(1)(2)遍历，不走(2)(1)if (m<=1){cout<<0;}else Dfs(2);cout<<anser;//system("pause");return 0;}

后来，给m限定了个定值,然而过了4个点

int main()
{int i;//读入数据cin>>n>>m;for (i=1;i<=m;i++) cin>>ct[i].from>>ct[i].to>>ct[i].anger;sort(ct+1,ct+m+1,Cmp);//for (i=1; i<=m; i++) cout<<ct[i].from<<' '<<ct[i].to<<' '<<ct[i].anger<<endl;//测试sortint k1 = ct[1].from;//int k2 = ct[1].to;//nd.jy1[k1] = 1;nd.jy2[k2] = 1;//直接初始化第一层，从(1)(2)遍历，不走(2)(1)m=2500;//就这里if (m<=1){cout<<0;}else Dfs(2);cout<<anser;//system("pause");return 0;}

搜索真的没前途了吗。。。。。。。。。。。。。。。。。。。。。。。。。这道题目。。。。。。。。。。。。。。。。。。。。

-------------------------------------------------------------------------------------------------------------------------------

在搜索里面，时间复杂度高的源头在于，当(1)(2)分割之后，(1,3)(2,4)和(1,4)(2,3)这两种情况不得不枚举，因为没有明确策略知道后面的谁在监狱1，谁在监狱2，也就是不知道怎么明确安排每一对怒气值的2人在各自哪个监狱。

也就是尝试，“从上往下”求解分配粗略的时候，因为要讨论的情况太多，导致进行不下去了。。。不得不转换思路了。。。。。

-----------------------------------------------------------------------------------------------------------------------------------

各自在哪个监狱不好确定，但是哪2个不能在一个监狱，是很好确定的，怒气值排序后，从高到低，尽可能把他们分开。。。。

就算用并查集实现集合来表示监狱1,2，依然 会面临谁在1谁在2的分配问题，是白搭的。。。。。。。。。。。。。。。。

应该用并查集，把谁和谁不能在一起用表示出来

样例：

集合4个： 1   2   3    4

第1组： 1 2 28351 

1-2   3  4

第2组： 3 4 12884

1-2 3-4

第3组： 1 3  6618

2-1 -  3-4

岂不是成了 1 2 3 4 都两两不在同一监狱？本来想表示的是：

1-2  3-4 这样的一种集合关系，1 2,13,34不能在一起，但是2-3在一个集合里岂不也被定义成了不能在一起

|

3

----------------------------------------------------------------------------------------------

不能在一个监狱的表示方式：

第1组：1 2 如果 1为黑 那2为白

第2组：3 4 如果 3为黑2 那4为白2

第3组：1 3 两者均虽已涂色，但不是同一系颜色，那以1为准，3变为白，4变为黑

第4组：2 3 两者均已涂色，且是同一系列颜色，2为白，3为白，冲突，输出

-----------------------------------------------------------------------------------------------

       1    2     3     4

      -1    -1  -1    -1

k=0

第1.2组：0 1 2 3 表示 第0集合：0/2=1/2=0 为1,2点 第1集合 ：2/2=3/2=1，为3,4点，且集合内部奇点和偶点表示不能放在一个监狱，对应的奇数的肯定在一个监狱，偶在一个

第3组1，3执行后：1为0 3为2 不在同一集合，集合合并，且刷新第1集合的点为：0 1 1 0 表示 12 点不共存 13 点不共存 3 4点共存同时也得出2 3必须一起 14必须一起

算法过程：k*2 k*2+1 表示集合k中互相不能在一起的元素

初始都为-1 表示都还没确定分配

从1..m循环

   查看from to 是否都为-1，如果都为-1 

          from=k*2;to=k*2+1;k++;这样from,to就被分到了集合k中

  否则 如果 from 为0 to 不为-1// from还没确定，但是to已经确定不能和谁在一起，以及必须和谁在一起了

         if to%2==-1 then from=to-1 else from=to+1

  否则 如果from不为-1 to 为-1

       if from%2==-1 then to=from-1 else to=from+1

  否则 如果from 不为-1 to 不为-1 //表示这两者都有确定不能和谁在一起

      if from/2==to/2 //表示2者在同一集合里面

            if from==to then print from和to的怒气值  ，结束//两者一致，表示之前已经确定在一个监狱了，而和当前想拆冲突

      if from/2 != to/2 //表示2者不在同一集合里面

           则将 根据 from 修改 to为to2 且把集合k2=to/2里面所有和to相等都改为to2 所有和to不等的改为from//时间复杂度为O(n)循环找一遍的话

循环结束

print 0

时间复杂度 应该是O(m^2) 居然过了

AC代码：

//#include <StdAfx.h>
#include <stdlib.h>//system("pause")
#include <stdio.h>
#include <string>//string
#include <iostream>
#include <cstring>//memset
#include <algorithm>//sort
using namespace std;typedef struct ChongTu{int from;int to;int anger;
} ChongTu;
typedef struct Node{int jy1[20001];int jy2[20001];
}Node;ChongTu ct[100001];
int jh[20001];//保存集合的数组
Node nd,isUsed;
int n,m,anser=1e9;
int flag = 0;
int k;int Cmp(ChongTu x, ChongTu y)
{if (x.anger>y.anger)return 1;else return 0;
}
int main()
{int i,j;//读入数据cin>>n>>m;for (i=1;i<=m;i++) cin>>ct[i].from>>ct[i].to>>ct[i].anger;sort(ct+1,ct+m+1,Cmp);//for (i=1; i<=m; i++) cout<<ct[i].from<<' '<<ct[i].to<<' '<<ct[i].anger<<endl;//测试sortmemset(jh,-1,sizeof(jh));//初始化for (i=1;i<=m;i++){int from = ct[i].from;int to  = ct[i].to;if (jh[from]==-1 && jh[to]==-1) //都还没确定不能和谁在一起{jh[from]=k*2;jh[to] = k*2+1;k++;//k从集合0 变为集合1}else if (jh[from]==-1 && jh[to]!=-1)//to确定了,from确定为to的同一集合且标记为to不能在一起的标志{jh[from] = jh[to]%2==0 ? jh[to]+1 :jh[to]-1; }else if (jh[from]!=-1 && jh[to]==-1)//from确定了，to还没有{jh[to] =jh[from]%2==0 ? jh[from]+1 : jh[from]-1;}else if (jh[from]!=-1 && jh[to]!=-1)//都有确定了{if (jh[from]/2==jh[to]/2)//如果两个在同一个集合{if (jh[from]%2==jh[to]%2)//如果两者相等表示，他两应该已经确定要关在一个监狱，也就是颜色一致，但目前要拆，矛盾输出{cout<<ct[i].anger;//	system("pause");return 0;}}else //两者没 在同一集合则合并 比如 1 2 3 4  集合0的0 1 集合1 的0 1{//将to的集合全部改为from的，并且和to值相等的全改为from的敌对，to不等的全改为fromint f0 = jh[from];int f1 = jh[from]%2==0 ? jh[from]+1 : jh[from]-1;int t0 = jh[to];int t1 = jh[to]%2 ==0 ? jh[to]+1 : jh[to]-1;for (j=1; j<=i; j++){if (jh[ ct[j].from] == t0) jh[ct[j].from]=f1;if (jh[ ct[j].to] == t0) jh[ct[j].to]=f1;if (jh[ ct[j].from ] == t1)  jh[ct[j].from]=f0;if (jh[ ct[j].to ] == t1) jh[ct[j].to]=f0;}}}}cout<<0;//走完循环，意味着切割完毕//system("pause");return 0;}

其实，上面这个就是个不停的染色，变色的过程

-------------------------------------------------------------------------

在利用 可以确定哪些人不能关在一个监狱 求解的过程中，分析解集合的意义如下

jh[x] 存储的是x节点的集合信息+他自身标注自己不能和谁在一起，能和谁一起的信息

集合信息是： jh[x] / 2 

节点自身信息：jh[x]%2 也就是利用奇偶性，或者说，同属jh[x]/2里面的点，要么值为jh[x] 要么为jh[x]%2==0 ? jh[x]+1 :jh[x]-1; 相同代表同一监狱，不同意味不同监狱，不需要知道让人头疼的到底在哪个监狱，只需要知道可以轻松获知的和谁在一个，和谁不在一个，最后分成2批后，分开关在哪个监狱都是合乎题目要求的

分析上述存储结构和算法，其实关键点就在于

1、判断from和to是否是同一集合

2、如果同属一个集合，那from和to两者的本身性质是否一样，也就是奇偶性是否相同（相同则也就意味着他2已经一个监狱了，再拆开矛盾，不同则意味着可行）

3、如果不是同一集合，那么两个集合就需要合并

4、如果不是同一集合，集合合并的同时还要依据from的奇偶性，来设置to所在集合所有元素的奇偶性

     如果from 为奇，则to所在集合中和to性质相同的所有点，都应更改为偶；和to不同的，都应修改为奇

    如果From为偶，则to所在集合中和to性质相同的所有点，都应更改为奇；和to不同的，都应修改为偶

-------------------------------------

集合的合并，2点是否同一集合，这些特征，擅长此道的非并查集了吧？？？？？？

关键在于，点本身的奇偶性，怎么样来表述

可以再开一个数组来保存节点当前的奇偶性也就是01 复杂度为O(M*N)

//#include <StdAfx.h>
#include <stdlib.h>//system("pause")
#include <stdio.h>
#include <string>//string
#include <iostream>
#include <cstring>//memset
#include <algorithm>//sort
using namespace std;typedef struct ChongTu{int from;int to;int anger;
} ChongTu;
typedef struct Node{int jy1[20001];int jy2[20001];
}Node;ChongTu ct[100001];
int father[20001];//保存集合组成信息
int jiou[20001];//保存节点的奇偶性
//Node nd,isUsed;
int n,m,anser=1e9;
int flag = 0;
int k;int Cmp(ChongTu x, ChongTu y)
{if (x.anger>y.anger)return 1;else return 0;
}
int Find(int x)
{//递归终止条件if (x==father[x]) //根节点，返回return x;int fatherX = father[x];//在树中向上递归一层int rootX = Find(fatherX);//找到双亲节点的根节点，那么肯定也是孩子节点的根节点,每一层向上递归，直到//根节点返回，返回root，那么在每一层的rootX均是最终的根节点root,//顺手压缩路径，之所以可以压缩是因为集合无序，形态不重要，在查询和合并操作里面并不影响father[x] = rootX;//让每个路径上的节点都指向根节点return rootX;}
int main()
{int i,j;//读入数据cin>>n>>m;for (i=1;i<=m;i++) cin>>ct[i].from>>ct[i].to>>ct[i].anger;sort(ct+1,ct+m+1,Cmp);//for (i=1; i<=m; i++) cout<<ct[i].from<<' '<<ct[i].to<<' '<<ct[i].anger<<endl;//测试sortmemset(jiou,-1,sizeof(jiou));//初始化为全部未确定for (i=1;i<=n;i++) father[i] = i;//并查集初始化每个节点为根节点，也就是独立的集合//开始集合的合并，合并那些不能在一起的for (i=1; i<=m; i++){int from = ct[i].from;int to = ct[i].to;//判断2者是否都还没确定，也等价于2者分属不同集合if (jiou[from]==-1 && jiou[to]==-1)//合并2者{father[from] = to;//集合合并jiou[from]=0;jiou[to] = 1;//确定各自性质，其实奇偶反过来写10也一样}else if (jiou[from]==-1 && jiou[to]!=-1)//表示from还没确定，是个独立集合，to已经在一个集合里，两者分属于不同集合{father[from] = to;//这里不能写成father[to] = from;,原因在于并查集在利用树表示集合的时候，只有根节点没有双亲，father[root]是空的//其他的孩子节点的father[x] 都指向了双亲节点，在不知道to是否是根节点的情况下，写fahter[to] = from;会将to从原树中剥离出来，脱离集合//而from是一个只包含自己的集合，根节点就是他自己所以可以father[from]=tojiou[from] = jiou[to] ==0 ? 1 : 0;//如果to为偶，则from为奇，to为奇，则From为偶 }else if (jiou[from]!=-1 && jiou[to]==-1)//表示from确定。to没确定，两者属于不同集合{father[to] = from;//理由同上，不能写成father[from]=to;jiou[to] = jiou[from]==0 ? 1 : 0;}else if (jiou[from]!=-1 && jiou[to]!=-1) //都没确定，其实意味着分属于2个元素个数大于1的集合{int rootFrom = Find(from);//找到from根节点int rootTo = Find(to);//找到to的根节点if (rootFrom==rootTo)//意味着两者属于同一集合！！！！！！！！！！！！{if (jiou[from]==jiou[to]) {//意味着这2个已经确定为同一个监狱了，但当前想拆开，矛盾，输出cout<<ct[i].anger;//system("pause");return 0;}}else//两者属于不同集合，集合合并，并更改集合里面元素的性质{//更改to中集合元素性质//两者奇偶不同则不用更改，直接合并即可，相同则需要将to中的整体翻转if (jiou[from] == jiou[to]){for (j=1; j<=n; j++)//降低搜索个数{if (Find(j)==rootTo)//同一集合则翻转奇偶{jiou[j] = jiou[j]==0?1:0;}//if (Find(ct[j].to) == rootTo){//	jiou[ct[j].to] = jiou[ct[j].to]==0?1:0;}}}//翻转完毕后合并2个集合father[rootFrom] = rootTo;//根节点的合并}}}cout<<0;//走完循环，意味着切割完毕//system("pause");return 0;}

---------------------------------------

接上--------

上面的时间复杂度为o(n*m)，关键点就在于，在合并2个集合的时候，要根据from 来刷新to中所有节点的奇偶性，比如from为0 to 为0 那合并后，to该为1，to所在集合所有0都变为1，所有1都变为0

这个合并集合的同时要刷新集合，并没有凸显并查集的优势，问题产生的源头就在于这里 表示 不能在一起，利用的同在一个集合且两者奇偶性不同，利用的是相对性

比如集合里面如1 为0 2 为1 和1为1 2为0 表示的是一回事，到底集合里的犯人1和谁在一起，不能和谁在一起，要靠和1奇偶性相同与否来判断，而不是说，根据犯人“自身”的一个不变化的量来确定

如果要不刷新，就必须找个 元素 本身不用变化的量，来表述，元素1和元素2不能在一起的这个性质

-----------------------------------------

将原先的相对关系固化到元素本身 比如 1,2 同一集合，1,2奇偶不同，干脆定义个1 偶数1 2 偶数2 

其中偶数X表示，谁和偶数X在一个集合，就表示，谁不能和对应的x在同一个监狱

那样在合并from to所在的集合时，from和to当做奇数的from 和to

如果2者不在同一集合，则意味着from to可以确定不在一起，集合合并，合并From所在集合和偶数to所在的集合，来表示to和from不能在一起，这样的话from和偶数to性质，奇偶相反，不用刷新；同样to也和偶数From合并表示from和to不能在一起，这样双方相互合并，才能明确表示清楚 from:0 -to 1 to 0 -from 1这两种等价的状态，也就是，问谁 不能和to在一起，只需要看偶数to里面的非偶数值，问谁不能和from在一起，只需要看偶数From所在集合的非偶数，这样才能表示from to相互不在一起的这个关系

----------------------------------------

在并查集里面，开了一个2*n的数组

用1+n 来表示这个1的偶数1，也就是谁不能和1在一起

在看题解过程中，一直很难理解，想到这种解法的人，到底是如何想到这种表示方法的，如何想到开2*n数组，来实现并查集合并操作的无刷新

包括以上所有的思维过程，都是在往下找啊找，直到写到这里，还是依然不很能融会贯通这种实现

--------------------------------------------------

//#include <StdAfx.h>
#include <stdlib.h>//system("pause")
#include <stdio.h>
#include <string>//string
#include <iostream>
#include <cstring>//memset
#include <algorithm>//sort
using namespace std;typedef struct ChongTu{int from;int to;int anger;
} ChongTu;
ChongTu ct[100001];//这么大的数据量必须放到全局变量，在空间提前分配，局部定义报错
int n,m;
int father[40001];//按照2*n来开数组，保存并查集，也就是对应点x的双亲节点为father[x]
//拿来给sort的比较函数
int Cmp(ChongTu a, ChongTu b)
{if (a.anger>b.anger) return 1;else return 0;
}
//找根节点同时路径压缩下
int Find(int x)
{if (x==father[x]) return x;//如果自身和双亲节点一样，则为根节点，输出else //如果自身和双亲节点不一样，向上递归找根节点{int fatherX = father[x];//找x的双亲节点int rootFatherX = Find(fatherX);//找到的双亲节点的根节点肯定也是x的根节点//路径压缩，整个路径x>fatherX>fatherfatherX...>root//只有找到root递归结束返回也就是每一次递归的rootFatherX1=rootFaherX2=...=root//并查集这棵树，形态怎么样的无所谓，因为最终表示的是一个集合，集合无序，只要//节点x,y在同一颗树上，那么他们必然拥有共同的根节点，也就是他们同属一个集合//并查集：查询是否同一个结合，合并2个集合，也就是完成了这个2个操作//所以我们在每一层递归后，都将当前节点的双亲节点修改为根节点，达到降低树高度//优化下次查询的目的，每次查询的复杂度本身就是和树高相关，和路径上节点数相关//高度越小，路径节点数越少，递归也越可以尽早结束father[x] = rootFatherX;return rootFatherX;//返回最终结果		}/*上面的写法，直观但是不简练，更简单写法：return x==father[x] ? x : father[x]=Find(father[x]);*/
}int main()
{int i,j,k;//读入数据cin>>n>>m;for (i=1; i<=m; i++) cin>>ct[i].from>>ct[i].to>>ct[i].anger;//排序，按照怒气值从大到小sort(ct+1,ct+m+1,Cmp);//for (i=1; i<=m; i++) cout<<ct[i].from<<' '<<ct[i].to<< ' ' <<ct[i].anger<<endl;//测试排序//开始按照怒气值大小，把不能在一起的放在一个集合里面，直到出现冲突//初始化for (i=1; i<=n*2;i++) father[i]=i;//每个节点都弄成根节点for (i=1; i<=m; i++){int rootFrom = Find(ct[i].from);//找第i个冲突中罪犯from的所在集合的根节点int rootTo = Find(ct[i].to);//找第i个冲突中罪犯to的所在集合的根节点//这两个罪犯已经在同一个集合，也就是意味着，在满足按照1..i-1的罪犯拆开的情况下//i.from 和 i.to 必须已经在同一个监狱了//而当前想i.from 和 i.to 拆开，让他们不在同一监狱，会导致前面i..i-1某个较大冲突的不成立//也就是i这对不能拆，只能在一起，那也就是找到了，题目里希望的尽可能小的最大冲突值//输出if (rootFrom==rootTo){cout<<ct[i].anger;//system("pause");return 0;}//rootFrom!=rootTo则意味着from和to没在一个集合，意味着他两在不违背1...i-1拆开的//基础上可以不在同一个监狱，怎么样表示他2个不在同一监狱呢？//让from和to+n(和to+n在一个集合的，就表示不能和to在同一个监狱)在一个集合//同样让to 和from+n在一个集合来表示to和from不能在同一个监狱//并查集的合并操作，根节点相连int rootToN = Find(ct[i].to+n);//to+n表示不能和to在同一个监狱，找它的根节点int rootFromN = Find(ct[i].from+n);//from+n表示不能和from在同一监狱，找它的根节点father[rootFrom] = rootToN;//from和to+n集合合并，表示From和to不在一个监狱father[rootTo] = rootFromN;//to和from+n集合合并，表示to和from不在一个监狱}cout<<0;//走完循环，意味着n个罪犯有怒气矛盾的都拆开了，没有冲突//system("pause");return 0;
}

--------------------------------

以前很多题目的并查集，之所以可以直接合并而无刷新操作，是感觉他们同一类别或者说同一“”属性“”，如同数组的每个元素类型一致，而在本题中，如果是同在一座监狱的行成一个集合，那么显然直接合并就可以；题目能确定的是不在一个监狱放在一个集合里面，

“同在”：类型X + 类型X 合并操作是+    

 “不在”：类型X-类型X  转成 类型X+(对立类型X) 这样每个X本身性质不变可以直接合并而无需刷新改变操作

？？？？？？？？？？？？？？？？？？？以上全是歪理感受

--------------------------------------------

在由下而上，由结果倒推来验证条件，逼近问题里面，还有一个经典的算法是二分答案

题目明确来分谁在哪个监狱，从上往下推结果不好走，那猜测结果，看哪个冲突值是所有冲突里面的最小值，最大值里找最小值，可以满足题意，

二分求解答案三特征：结果的可能范围要区间明确， 离散，单调有序

冲突值肯定在【0,100000】里，整数所以离散，整数所以单调有序

----------------------------------

验证枚举的怒气值的条件呢？比如预期的怒气值是5000,5000这个怒气值上限的情况下，能把所有犯人分到2监狱吗，也就是冲突对里面所有大于等于5000的边，能把图分成个二分图吗

如果怒气值大于等于X的边可以将其分为二分图，就就意味这个值是可以的，在找找还有没有比他更小的，如果分不了二分图，那就说明这个怒气值小了，在比他大的里面找找能分的

所以外层二分答案，判断预期结果是否可行，用的是二分图染色，看能否染成

------------------

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;const int N=20000+5;int n;struct E{int to,v;
};
vector<E>g[N];int color[N];
bool vis[N];
bool dfs(int colo,int p,int top){if(color[p]==-colo)return 1;color[p]=colo;if(vis[p])return 0;vis[p]=1;for(int i=0;i<(int)g[p].size();i++)if(g[p][i].v>top){if(dfs(-colo,g[p][i].to,top))return 1; }return 0;
}
bool tryit(int top){memset(color,0,sizeof(color));memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)if(!vis[i])if(dfs(1,i,top))return 0;return 1;
}int main()
{freopen("prison1.in","r",stdin);freopen("prison1.out","w",stdout);int m;scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);E pu=(E){b,c};g[a].push_back(pu);pu.to=a;g[b].push_back(pu);}
/*	for(int i=1;i<=n;i++){printf("%d:",i);for(int j=0;j<g[i].size();j++)printf("%d ",g[i][j].to);printf("\n");}*/int l=0,r=1000000000+1,mid;while(l<r){//[l,r);mid=(l+r)/2;
//		printf("%d %d %d\n",l,mid,r);if(tryit(mid)){r=mid;}else{l=mid+1;}}mid=(l+r)/2;printf("%d",mid);fclose(stdout);return 0;
}

-----------------------------------------

总结：1、深搜，广搜，因为只写了一个代码，对其时间空间复杂度的分析可能会存在些问题

            2、关键就是并查集的那种2*n   x和x+n这种解题思路，在脑子里一直串联不起来，形不成一个通路，怎么就可以这样表示了

  所以一直尝试分析是如何想到这种解法的，言语有些混乱不清，一如我的脑中乱序

           3、二分答案，是从小向上求解；并查集应该是从上往下，包括条件的变形：找谁和谁不能在一起；也是一个最初的条件？？？？

          4、论集合的查询合并效率，并查集，洋气

                论可以暴力枚举答案，如果可以二分一般都是log2 N * N的效率乃至更高吧

         5、题目里面既然透露着要对怒气值排序，起码时间复杂度的N*logN吧，所以设计一个N2或者n*logN效率的算法应该是可以ac的

         6、一旦数据量上100000,20000，是不是就意味深搜，广搜，暴力枚举就落伍了？？？？包括动归，动归开数组一般的n*n吧，所以这是不是一个暗示，暗示我们二分答案，二分图染色，并查集之类的，高效率策略了？？？？？

         7、虫食算那个，26个的字母，优化不好的搜索都能超时，那可想而知，这种数据量的题目，应该不会考察二分图染色，二分查找二分答案，并查集之类的吧？数据范围太小没意思了就，那估计想考的是不是就是模拟，枚举，搜索了？

        8、纯属猜测。。。。。。。。。。。。。。。。。。。。。。

------------------------

多有不当，望批评指正，共同进步。。。。。。。。。。。

end.....