正文

codevs5971打击犯罪x

云深不知处  云深不知处  2022-08-28  255

关键词：

题目描述 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

数据范围及提示 Data Size & Hint

n<=1000

技术分享

输出1（打击掉红色团伙)

分类标签 Tags 点此展开

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define Maxn 10100
 5 
 6 using namespace std;
 7 
 8 int n,t,r1,r2;
 9 int f[Maxn],group[Maxn];
10 int gx[Maxn][Maxn];
11 bool qwq;
12 
13 int find(int x)
14 {
15     return x == f[x] ? x : f[x]=find(f[x]);
16 }
17 
18 void In()
19 {
20     int p,k,q=0;
21     scanf("%d",&n);
22     t=n/2;
23     for(int i=1;i<=n;i++)//初始化 
24     {
25         f[i]=i;
26     }
27     for(int i=1;i<=n;i++)
28     {
29         cin>>p;
30         q++;
31         while(p>0)
32         {
33             p--;
34             scanf("%d",&k);
35             if(k>q) gx[q][++gx[q][0]]=k;//gx[q][0]进行储存q能够连接到的边数 
36         }
37     }
38     
39 }
40 
41 void QAQ()
42 {
43     for(int i=n;i>=1;--i)
44     {
45         memset(group,0,sizeof(group));//进行清空，便于记录    
46         for(int j=1;j<=gx[i][0];++j)
47         {
48             r1=find(i);
49             r2=find(gx[i][j]);
50             if(r2!=r1) f[r2]=r1;//合并
51         }
52         for(int qq=1;qq<=n;qq++)
53         {
54             group[find(qq)]++;    
55         }
56         for(int h=1;h<=n;h++)
57         if(group[h]>t)
58         {
59             qwq=1;
60         }
61         if(qwq==1)
62         {
63             printf("%d",i);
64             break;
65         }    
66     }
67 }
68 
69 int main()
70 {
71     In();
72     QAQ();
73     return 0;
74 }

hdu5971wrestlingmatch

题目链接：hdu5971WrestlingMatch题意：N个选手，M场比赛，已知x个好人，y个坏人，问能否将选手划分成好人和坏人两个阵营，保证每场比赛必有一个好人和一个坏人参加。题解：dfs染色。听说题意模糊？从样例来看，第一个例子应... 查看详情

codevs1515跳

http://codevs.cn/problem/1515/ (题目链接)题意　　给出一个棋盘，规定走到(x,y)的花费C(x,y)=C(x-1,y)+C(x,y-1)，x=0或y=0时C(x,y)=1。求从(0,0)走到(n,m)的路径上的花费和的最小值。Solution　　画画图很容易就会发现是个杨辉三角，我们假设${n... 查看详情

codevs1515:跳

题目描述Description邪教喜欢在各种各样空间内跳。现在，邪教来到了一个二维平面。在这个平面内，如果邪教当前跳到了(x,y)，那么他下一步可以选择跳到以下4个点：(x-1,y),(x+1,y),(x,y-1),(x,y+1)。而每当邪教到达一个点，他需要耗费... 查看详情

codevs2606约数和问题

题目描述DescriptionSmart最近沉迷于对约数的研究中。对于一个数X，函数f(X)表示X所有约数的和。例如：f(6)=1+2+3+6=12。对于一个X，Smart可以很快的算出f(X)。现在的问题是，给定两个正整数X,Y(X<Y)，Smart希望尽快地算出f(X)+f(X+1)+&helli... 查看详情

wrestlingmatchhdu-5971（思维+stl）

ProblemDescriptionNowadays,atleastonewrestlingmatchisheldeveryyearinourcountry.Therearealotofpeopleinthegameis"goodplayer”,therestis"badplayer”.Now,XiaoMingisrefereeofthewrestlingmatchandhehasalistoft 查看详情

codevs1842递归第一次

难度等级：白银1842递归第一次题目描述 Description同学们在做题时常遇到这种函数f(x)=5(x>=0)f(x)=f(x+1)+f(x+2)+1(x<0)下面就以这个函数为题做一个递归程序吧输入描述 InputDescription一个数表示f(x)中x值大家注意就一个数，前... 查看详情

codevs1842递归第一次

题目描述 Description同学们在做题时常遇到这种函数f(x)=5(x>=0)f(x)=f(x+1)+f(x+2)+1(x<0)下面就以这个函数为题做一个递归程序吧输入描述 InputDescription一个数表示f(x)中x值大家注意就一个数，前面代表样例编号输出描述 Out... 查看详情

hdu5971wrestlingmatch

WrestlingMatchTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):1031 AcceptedSubmission(s):390ProblemDescriptionN 查看详情

codevs——1842递归第一次

1842递归第一次时间限制:1s 空间限制:128000KB 题目等级:白银Silver题解题目描述 Description同学们在做题时常遇到这种函数f(x)=5(x>=0)f(x)=f(x+1)+f(x+2)+1(x<0)下面就以这个函数为题做一个递归程序吧输... 查看详情

codevs3729飞扬的小鸟x

3729飞扬的小鸟时间限制:1s 空间限制:128000KB 题目等级:黄金Gold 题目描述 Description输入描述 InputDescription输出描述 OutputDescription输出文件名为bird.out。共两行。第一行，包含一个整数，如果可以成功完成... 查看详情

codevs5929亲戚

5929亲戚时间限制:1s空间限制:128000KB题目等级:黄金Gold 题目描述Description若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。... 查看详情

codevs5958无x（搞事情）

这个名字我很想吐槽这个题目就特别厉害了！入下：5958无时间限制:1s空间限制:1000KB题目等级:大师Master 题目描述Description无输入描述InputDescription无输出描述OutputDescription无样例输入SampleInput无样例输出SampleOutput... 查看详情

bzoj[spoj5971]lcmsum

DescriptionGivenn,calculatethesumLCM(1,n)+LCM(2,n)+..+LCM(n,n),whereLCM(i,n)denotestheLeastCommonMultipleoftheintegersiandn.InputThefirstlinecontainsTthenumberoftestcases.EachofthenextTlinescontainani 查看详情

codevs-1073家族

题目描述 Description若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚... 查看详情

codevs1073家族

hdu5971二分图判定

WrestlingMatchTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):2097 AcceptedSubmission(s):756ProblemDescriptionN 查看详情

codevs2291糖果堆x

题目描述Description【Shadow1】第一题WJMZBMR买了很多糖果，分成了N堆，排成一列。WJMZBMR说，如果Shadow能迅速求出第L堆到第R堆一共有多少糖果，就把这些糖果都给他。现在给出每堆... 查看详情

codeves1214线段覆盖

思路：排序之后，对于当前这个ri，看是否能找到li1#include<bits/stdc++.h>2usingnamespacestd;34structnode{5intx,y,z;6}a[2002];78boolcmp(nodep,nodeq){9if(p.x==q.x)returnp.y<q.y;10returnp.x<q.x;11}12set<int>ss 查看详情