codevs 5971 打击犯罪 x
2024-09-05 17:14:19
题目描述 Description
某个地区有n(n<=1000)个犯罪团伙,当地警方按照他们的危险程度由高到低给他们编号为1-n,他们有些团伙之间有直接联系,但是任意两个团伙都可以通过直接或间接的方式联系,这样这里就形成了一个庞大的犯罪集团,犯罪集团的危险程度唯一由集团内的犯罪团伙数量确定,而与单个犯罪团伙的危险程度无关(该犯罪集团的危险程度为n)。现在当地警方希望花尽量少的时间(即打击掉尽量少的团伙),使得庞大的犯罪集团分离成若干个较小的集团,并且他们中最大的一个的危险程度不超过n/2。为达到最好的效果,他们将按顺序打击掉编号1到k的犯罪团伙,请编程求出k的最小值。
输入描述 Input Description
第一行一个正整数n。接下来的n行每行有若干个正整数,第一个整数表示该行除第一个外还有多少个整数,若第i行存在正整数k,表示i,k两个团伙可以直接联系。
输出描述 Output Description
一个正整数,为k的最小值
样例输入 Sample Input
7
2 2 5
3 1 3 4
2 2 4
2 2 3
3 1 6 7
2 5 7
2 5 6
样例输出
Sample Output
1
数据范围及提示
Data Size & Hint
n<=1000
输出1(打击掉红色团伙)
分类标签
Tags
点此展开
#include<iostream>
#include<cstdio>
#include<cstring>
#define Maxn 10100 using namespace std; int n,t,r1,r2;
int f[Maxn],group[Maxn];
int gx[Maxn][Maxn];
bool qwq; int find(int x)
{
return x == f[x] ? x : f[x]=find(f[x]);
} void In()
{
int p,k,q=;
scanf("%d",&n);
t=n/;
for(int i=;i<=n;i++)//初始化
{
f[i]=i;
}
for(int i=;i<=n;i++)
{
cin>>p;
q++;
while(p>)
{
p--;
scanf("%d",&k);
if(k>q) gx[q][++gx[q][]]=k;//gx[q][0]进行储存q能够连接到的边数
}
} } void QAQ()
{
for(int i=n;i>=;--i)
{
memset(group,,sizeof(group));//进行清空,便于记录
for(int j=;j<=gx[i][];++j)
{
r1=find(i);
r2=find(gx[i][j]);
if(r2!=r1) f[r2]=r1;//合并
}
for(int qq=;qq<=n;qq++)
{
group[find(qq)]++;
}
for(int h=;h<=n;h++)
if(group[h]>t)
{
qwq=;
}
if(qwq==)
{
printf("%d",i);
break;
}
}
} int main()
{
In();
QAQ();
return ;
}
最新文章
- ssh 不能连上服务器 hosts.deny没有没限制ip 找不到什么原因
- 使用Lucene开发自己的搜索引擎
- base64 加密
- 在ASP.NET MVC中验证checkbox 必须选中 (Validation of required checkbox in Asp.Net MVC)
- LINQ to PostgreSQL Tutorial
- 使用.netFx4.0提供的方法解决32位程序访问64位系统的64位注册表
- Violin 琴弦介绍
- HDU-1996-汉诺塔VI
- TIME_WAIT 另一种解决方式 SO_LINGER
- RDD概念、特性、缓存策略与容错
- Python 字符串增删改查的使用
- python requests 上传文件
- quartz简单定时任务【可以处理完一个任务才开启下一个线程】【我】
- AJAX 原生态
- Javascript MVC 学习笔记(一) 模型和数据
- U盘安装win7系统
- python操作mysql二
- javascript和jquery比较
- idea debug操作
- laravel 模型关联之(多对多)