NOIP2010关押罪犯[并查集|二分答案+二分图染色 | 种类并查集]

题目描述

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:
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
输出样例#1:
3512

说明

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

NOIP2010关押罪犯[并查集|二分答案+二分图染色 | 种类并查集]

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

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

并查集:

i的敌人集合为i+n,同一个敌人集合的人一定在同一个*

按怒气从大到小排序,依次考虑每对敌人,如果在同一个集合就输出,负责合并到对方的敌人集合里(因为是一个人的敌人)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=,M=;
int n,m,a,b,c,ans=;
struct edge{
int u,v,w;
}e[M];
int cnt=;
inline void add(int u,int v,int w){
cnt++;
e[cnt].u=u;e[cnt].v=v;e[cnt].w=w;e[cnt].u=u;
}
inline bool cmp(edge a,edge b){
return a.w>b.w;
}
int fa[N<<];
inline int findp(int x){
return x==fa[x]?x:fa[x]=findp(fa[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
sort(e+,e++m,cmp);
for(int i=;i<=n*;i++) fa[i]=i;
for(int i=;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
int f1=findp(u),f2=findp(v);
if(f1==f2){ans=w;break;}
fa[f1]=findp(v+n);
fa[f2]=findp(u+n);
}
printf("%d",ans);
}

二分图:

二分最小c值,二染色看能不能成立,两种二染色方法

不知道为什么tle两个。。。。。原来是忘记m<<1了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=,M=;
int n,m,a,b,c,ans=;
struct edge{
int v,w,ne;
}e[M<<1];
int cnt=,h[N];
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;
}
int col[N],W,w[M];
bool bi(int u){//printf("%d %d\n",u,col[u]);
for(int i=h[u];i;i=e[i].ne){
if(e[i].w<=W) continue;
int v=e[i].v;
if(col[u]==col[v]) return false;
if(!col[v]){
col[v]=-col[u];
if(!bi(v)) return false;
}
}
return true;
}
bool dfs(int u,int fa){
for(int i=h[u];i;i=e[i].ne){
if(e[i].w<=W) continue;
int v=e[i].v;
if(v==fa) continue;
if(col[u]==col[v]) return false;
if(!col[v]){
col[v]=-col[u];
if(!dfs(v,u)) return false;
}
}
return true;
}
bool check(){
for(int i=;i<=n;i++)
if(!col[i]){
col[i]=;
if(!bi(i)) return false;
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
ins(a,b,c);w[i]=c;
}
sort(w+,w++m);
int l=,r=m;
while(l<r){
int m=(l+r)/; W=w[m];//printf("m %d %d\n",m,w[m]);
memset(col,,sizeof(col));
if(check()) ans=w[m],r=m;
else l=m+;
}
if(l==&&r<l) cout<<;
else printf("%d",ans);
}



[2016-10-31]

也可以用种类并查集,和POJ1703差不多,最快

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e4+,M=1e5+;
int n,m,a,b,c,ans=;
struct edge{
int u,v,w;
bool operator <(const edge &r)const{return w>r.w;}
}e[M];
int cnt=;
inline void add(int u,int v,int w){
cnt++;
e[cnt].u=u;e[cnt].v=v;e[cnt].w=w;e[cnt].u=u;
}
int fa[N],v[N];
inline int find(int x){
if(x==fa[x]) return x;
int root=find(fa[x]);
v[x]=(v[x]+v[fa[x]])&;
return fa[x]=root;
}
inline void unn(int a,int b){
int f1=find(a),f2=find(b);
if(f1!=f2){
fa[f1]=f2;
v[f1]=(v[a]+v[b]+)&;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
sort(e+,e++m);
for(int i=;i<=n;i++) fa[i]=i,v[i]=;
for(int i=;i<=m;i++){
int a=e[i].u,b=e[i].v,w=e[i].w;
int f1=find(a),f2=find(b);
if(f1==f2&&v[a]==v[b]){ans=w;break;}
unn(a,b);
}
printf("%d",ans);
}
上一篇:swift 4 生成随机数的内置方法汇总


下一篇:挂多个class还是新建class —— 多用组合,少用继承