【寒假作业】【NOIP2010】关押罪犯

“敌人的敌人就是朋友”——毛泽东

恩毛主席领导我们做出了这道题233

首先很容易可以想到的是，按矛盾大小排序，优先分开矛盾大的，不行了就是最大答案

那么用一个并查集维护“朋友关系”

但是这道题只给了“敌人关系”怎么办呢

我们给每个人复制一个人作为敌人，编号为i+n

那么如果要标记两个人为敌人的话，只需要把两个人分别与对方的复制人结为朋友就可以了233

当然这道题也可以用带权并查集做啦233

// <prison.cpp> - 02/14/16 15:45:23
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int MAXN=20002;
const int MAXM=100002;
struct cp{
	int a,b,v;
}p[MAXM];
int f[MAXN<<1];
int gf(int x){
	if(f[x]!=f[f[x]])f[x]=gf(f[x]);
	return f[x];
}
bool cmp(cp a,cp b){return a.v>b.v;}
int main(){
	freopen("prison.in","r",stdin);
	freopen("prison.out","w",stdout);
	int n=getint(),m=getint();
	for(int i=1;i<=n<<1;i++)f[i]=i;
	for(int i=0;i<m;i++)p[i].a=getint(),p[i].b=getint(),p[i].v=getint();
	sort(p,p+m,cmp);
	for(int i=0;i<m;i++)
		if(gf(p[i].a)==gf(p[i].b)){printf("%d",p[i].v);return 0;}
		else f[f[p[i].a]]=gf(p[i].b+n),f[gf(p[i].a+n)]=f[p[i].b];
	printf("0");
	return 0;
}

// <prison.cpp> - 02/14/16 15:45:23

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=20002;

const int MAXM=100002;

struct cp{

int a,b,v;

}p[MAXM];

int f[MAXN<<1];

int gf(int x){

if(f[x]!=f[f[x]])f[x]=gf(f[x]);

return f[x];

}

bool cmp(cp a,cp b){return a.v>b.v;}

int main(){

freopen("prison.in","r",stdin);

freopen("prison.out","w",stdout);

int n=getint(),m=getint();

for(int i=1;i<=n<<1;i++)f[i]=i;

for(int i=0;i<m;i++)p[i].a=getint(),p[i].b=getint(),p[i].v=getint();

sort(p,p+m,cmp);

for(int i=0;i<m;i++)

if(gf(p[i].a)==gf(p[i].b)){printf("%d",p[i].v);return 0;}

else f[f[p[i].a]]=gf(p[i].b+n),f[gf(p[i].a+n)]=f[p[i].b];

printf("0");

return 0;

}

说点什么