刚开始做的时候看到最小值这几个字,我们就应想到用贪心的想法,我们应该尽量的把先影响力高的两的犯人关到不同的监狱,直到发现有两个犯人已经被分配到相同的监狱,这两个犯人之间的影响力就是这题的答案。
二分法
二分法大家肯定都不陌生,这题只要对影响力进行二分,对于在二分出来的影响力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;
} |