刚开始做的时候看到最小值这几个字，我们就应想到用贪心的想法，我们应该尽量的把先影响力高的两的犯人关到不同的监狱，直到发现有两个犯人已经被分配到相同的监狱，这两个犯人之间的影响力就是这题的答案。
二分法
二分法大家肯定都不陌生，这题只要对影响力进行二分，对于在二分出来的影响力X，只要是犯人之间的影响力小于X就判断在可容忍范围内，可将其关到同一监狱内，反之则必须分到不同监狱。时间最多应是O(log1,000,000,000)，应还在时间范围内。
以下代码来自http://blog.csdn.net/cynthia_wjyi/article/details/47125015
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node{
int y,z,next;
}e[200020];
int tot,item,n,m;
int head[20005],b[20005],a[100005];
bool pd;
int cmp(int a,int b){return a<b;}
void insert(int x,int y,int z)
{
e[++tot].y=y;
e[tot].z=z;
e[tot].next=head[x];
head[x]=tot;
}
void dfs(int x,int data)
{
if(pd==false)return;
b[x]=data;
for(int i=head[x];i!=0;i=e[i].next)
{
if(e[i].z>item)
{
if(b[e[i].y]==-1)dfs(e[i].y,1-data);
else
if(b[e[i].y]==data){pd=false;return;}
}
}
}
bool work(int midd)
{
memset(b,-1,sizeof(b));
pd=true;
item=a[midd];
for(int i=1;i<=n;i++)
if(b[i]==-1)dfs(i,0);
return pd;
}
int main()
{
scanf("%d%d",&n,&m);
memset(head,0,sizeof(head));
int x,y,z;
tot=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
insert(x,y,z);
insert(y,x,z);
a[i+1]=z;
}
// for(int i=1;i<=tot;i++)cout<<e[i].y<<' '<<e[i].z<<' '<<e[i].next<<endl;
a[1]=0;
sort(a+1,a+1+m,cmp);
// for(int i=1;i<=m+1;i++)cout<<a[i]<<' ';
// cout<<endl;
int l=1,r=m+1,mid;
while(l<r)
{
mid=(l+r)/2;
// cout<<l<<' '<<r<<' '<<mid<<endl;
if(work(mid)==true)r=mid;
else l=mid+1;
}
printf("%d\n",a[l]);
} |
并查集
这题我乍一看以为是二分图，其实用并查集的思想就可以做。
- 对于并查集的判断顺序，通过贪心的思想得出是要从大到小，保证答案最小。所以要先对于影响力对每一对犯人进行排序。
- 对于每个犯人我们可以创造一个他的镜像，比如犯人X和犯人Y，我们需加入犯人Px和犯人Py。
- 在操作过程中我们只需不断将X、Py并入一个集合，同样将Y、Px也并入一个集合。在发现X，Y已处于同一集合时就说明他们已经被分配到相同的监狱，这时他们之间的影响力即是答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct sd
{
int x,y,z;
}hate[100100];
int father[50000];
bool com (sd a, sd b)
{
return a.z > b.z;
}
void start(int n)
{
for (int i = 1;i <= n; i++) father[i]=i;
}
int xfind(int x)
{
return father[x] == x ? x : xfind(father[x]);
}
void un(int a, int b)
{
father[xfind(a)] = xfind(b);
}
int main(void)
{
int i,n,m;
scanf("%d%d", &n, &m);
start(n*2);
int po=m;
while (m--) scanf("%d%d%d",&hate[m].x,&hate[m].y,&hate[m].z);
sort(hate+1,hate+po+1,com);
int ans=0;
for (i=1;i<=po;i++)
{
if (xfind(hate[i].x)==xfind(hate[i].y))
{
ans=hate[i].z;
break;
}
un(hate[i].x,hate[i].y+n);
un(hate[i].y,hate[i].x+n);
}
printf("%d", ans);
return 0;
} |