NOIP 2010 关押罪犯

一开始的想法是二分答案，然后用check函数检验是否可以实现。

01 int check(long limit)
02 {
03     long i;
04     memset(arrange,0,sizeof(arrange));
05     for(i = 0;i < ecount;i ++)
06     {
07         if(edge[i].c > limit)
08         {
09             if(arrange[edge[i].b] == 0 && arrange[edge[i].e] == 0)
10             {
11                 arrange[edge[i].b] = 1;  //此处有错误，因为不能确定edge[i].b一定放在第一个监狱。
12                 arrange[edge[i].e] = 2;
13             }
14             else if(arrange[edge[i].e] == 0)
15             {
16                 arrange[edge[i].e] = 3 - arrange[edge[i].b];
17             }
18             else if(arrange[edge[i].b] == 0)
19             {
20                 arrange[edge[i].b] = 3 - arrange[edge[i].e];
21             }
22             else if(arrange[edge[i].e] == arrange[edge[i].b])
23                 return 0;
24         }
25     }
26     return 1;
27 }

显然，这个算法存在问题，实际测试中只通过两个数据。

让我们再把题目看一下。注意到只有两个监狱，并且每个罪犯必须放在某一个监狱中，那么，可以想出一种很直接的算法。

1、创造n个监狱，每个监狱里放置一个罪犯。
2、对输入数据按照激烈程度从大到小排序。
……本人语文不太好，所以直接上代码了：

读者请自行分析separate数组的作用（本来想写的，可惜表达能力不好）

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04
05 typedef struct element
06 {
07     long b,e,c;
08 }element;
09
10 element edge[100005] = {};
11 int p[20010];
12 long separate[20010] = {};
13 long ecount = 0;
14 long M,N;
15
16 void addedge(long a,long b,long c)
17 {
18     edge[ecount].b = a;
19     edge[ecount].e = b;
20     edge[ecount].c = c;
21     ecount ++;
22 }
23
24 long getp(long x)  //并查集的应用
25 {
26     if(x != p[x])
27     {
28         p[x] = getp(p[x]);
29     }
30     return p[x];
31 }
32
33 void merge(long x,long y)
34 {
35     p[getp(x)] = p[getp(y)];
36 }
37
38 int cmp(const void *a,const void *b)
39 {
40     return (((element *)b)->c - ((element *)a)->c);
41 }
42
43 int main()
44 {
45     scanf("%ld%ld",&N,&M);
46     long i;
47     long a,b,c;
48     for(i = 1;i <= N;i ++)
49         p[i] = i;
50     for(i = 0;i < M;i ++)
51     {
52         scanf("%ld%ld%ld",&a,&b,&c);
53         addedge(a,b,c);
54     }
55     qsort(edge,ecount,sizeof(element),cmp);
56     for(i = 0;i < M;i ++)  //这应该是一个“贪心”算法
57     {
58         if(getp(edge[i].b) == getp(edge[i].e))
59         {
60             printf("%ld\n",edge[i].c);
61             exit(0);
62         }
63         if(separate[edge[i].b] == 0 && separate[edge[i].e] == 0)
64         {
65             separate[edge[i].b] = edge[i].e;
66             separate[edge[i].e] = edge[i].b;
67         }
68         else if(separate[edge[i].b] == 0)
69         {
70             separate[edge[i].b] = edge[i].e;
71             merge(edge[i].b,separate[edge[i].e]);
72         }
73         else if(separate[edge[i].e] == 0)
74         {
75             separate[edge[i].e] = edge[i].b;
76             merge(edge[i].e,separate[edge[i].b]);
77         }
78         else if(separate[edge[i].e] != 0 && separate[edge[i].b] != 0)
79         {
80             merge(edge[i].e,separate[edge[i].b]);
81             merge(edge[i].b,separate[edge[i].e]);
82         }
83     }
84     printf("0\n");  //别忘了0的情况
85     return 0;
86 }

不过，上述算法的正确性比较难证明。因此，介绍另一种方法：二分答案+宽搜染色。
直接看代码了。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 typedef struct node
006 {
007     long b;
008     long c;
009     struct node *next;
010 }node;
011
012 node *first[20010] = {};  //邻接表
013 int color[20010] = {};  //所在监狱，-1 or 1，0表示还没有确定
014 long M,N;
015
016 void addedge(long a,long b,long c)
017 {
018     node *p;
019     p = malloc(sizeof(node));
020     p->c = c;
021     p->b = b;
022     p->next = first[a];
023     first[a] = p;
024 }
025
026 long queue[100000];
027 long head,tail;
028
029 void enqueue(long n)
030 {
031     queue[tail ++] = n;
032 }
033
034 long dequeue()
035 {
036     return queue[head ++];
037 }
038
039 int dye(long k,long limit)  //宽搜，染色
040 {
041     node *p;
042     long now;
043     color[k] = 1;
044     head = tail = 0;
045     enqueue(k);
046     while(head < tail)
047     {
048         now = dequeue();
049         for(p = first[now];p != NULL;p = p->next)
050         {
051             if(p->c > limit)
052             {
053                 if(color[p->b] != 0)
054                 {
055                     if(color[p->b] == color[now])   return 0;  //发现矛盾，返回方案失败
056                 }
057                 else  //节点还没有被染色
058                 {
059                     color[p->b] = -1 * color[now];  //放在不同的监狱里
060                     enqueue(p->b);
061                 }
062             }
063         }
064     }
065     return 1; //方案成功
066 }
067
068 int check(long limit)
069 {
070     long i;
071     memset(color,0,sizeof(color));
072     for(i = 1;i <= N;i ++)  //有可能图是非连通的
073     {
074         if(color[i] == 0)
075         {
076             if(dye(i,limit) == 0)
077                 return 0;
078         }
079     }
080     return 1;
081 }
082
083 int main()
084 {
085     scanf("%ld%ld",&N,&M);
086     long i;
087     long a,b,c;
088     long l,r,mid;
089     l = r = 0;
090     for(i = 0;i < M;i ++)
091     {
092         scanf("%ld%ld%ld",&a,&b,&c);
093         addedge(a,b,c);
094         addedge(b,a,c);
095         if(c > r)   r = c;  //确定上界
096     }
097     while(l < r)  //二分
098     {
099         mid = (l + r) / 2;
100         if(check(mid))
101             r = mid;
102         else
103             l = mid + 1;
104     }
105     printf("%ld\n",l);
106     return 0;
107 }

上面这种解法的中心思想是根据囚犯不能在一起的关系构造图，然后用染色（BFS，DFS都可以，不能在一起的囚犯要求使用不同的颜色）判断是否为二分图。

测试表明，实用贪心+并查集的效率略高于二分+宽搜染色。前者计算10个数据总时间1.1s，后者1.3s。