洛谷P1525 关押罪犯

题目描述

S 城现有两座*，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一*，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。

每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入输出格式

输入格式：

输入文件的每行中两个数之间用一个空格隔开。第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证1<aj=<=bj<=N ，0 < cj≤ 1,000,000,000，且每对罪犯组合只出现一次。

输出格式：

共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内*中未发生任何冲突事件，请输出0。

输入输出样例

输入样例#1：

输出样例#1：

说明

【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512（由2 号和3 号罪犯引发）。其他任何分法都不会比这个分法更优。

洛谷P1525 关押罪犯

【数据范围】对于30%的数据有N≤ 15。对于70%的数据有N≤ 2000，M≤ 50000。对于100%的数据有N≤ 20000，M≤ 100000。

再经典不过的一道题

两种做法：

1.并查集

　　对于每个点存两个集合，一个是和他同*的，一个是和他不同*的

　　将怨恨值从大到小排，循环每个怨恨关系，要防止冲突的出现，就要使两人不在同一*中，并且与其中一个人不在同一*的人一定与另一个人在同一*

　　如果查到怨恨关系对应的两个人已经在统一*中了，由于怨恨关系是从大到小排列的，所以这一定是最大的一个，直接输出

2.二分+染色

　　题目要求最小化最大值，不难想到要用二分答案

　　由于只有两个*存在，染色就只需要染两种，分别对应两个*中的人

　　答案的最大可能值和最小可能值很显然，然后就是判断的问题了

　　判断也不难，就是神搜与其有关系的人，只要怨恨值大于期望值，就把他俩放到不同*里，如果两人已经被安排到同一个*，则说明这个期望值是不可行的

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 20000*3
#define maxm 100000*3
int fa[maxn],n,m;
struct node{int from,to,v;}e[maxm];
int cmp(node a,node b){return a.v>b.v;}
int find(int x){
if(fa[x]==x)return fa[x];
else return fa[x]=find(fa[x]);
}
int main(){
    scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        e[i].from=x;e[i].to=y;e[i].v=z;
    }
    sort(e+1,e+m+1,cmp);
for(int i=1;i<=n*2;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int f1=find(e[i].from);
int f2=find(e[i].to);
if(f1==f2){
            printf("%d",e[i].v);
return 0;
        }
        fa[f1]=find(e[i].to+n);
        fa[f2]=find(e[i].from+n);
    }
    printf("0");
return 0;
}

并查集

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxm 100010
#define maxn 20010
int n,head[maxm*2],m,num,l,r,vis[maxn];
struct node{
int to,pre,v;
}e[maxm*2];
bool flag;
void Insert(int from,int to,int v){
    e[++num].to=to;
    e[num].v=v;
    e[num].pre=head[from];
    head[from]=num;
}
void dfs(int fa,int now,int limit){
if(flag)return;
for(int i=head[now];i;i=e[i].pre){
int to=e[i].to;
if(e[i].v>limit&&to!=fa){
if(!vis[to]){
                vis[to]=-vis[now];
                dfs(now,to,limit);
            }
else if(vis[to]==vis[now]){
                flag=1;
return;
            }
        }
    }
}
bool check(int x){
    memset(vis,0,sizeof(vis));flag=false;
for(int i=1;i<=n;i++){
if(!vis[i]){
            vis[i]=1;
            dfs(i,i,x);

        }
    }if(flag)return false;
return true;
}
int main(){
    scanf("%d%d",&n,&m);int x,y,z;
for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        r=max(r,z);
        Insert(x,y,z);
        Insert(y,x,z);
    }
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))r=mid-1;
else l=mid+1;
    }
    printf("%d",l);
}

二分+染色

秒客网

洛谷P1525 关押罪犯

题目描述

输入输出格式

输入输出样例

说明

两种做法：

相关文章