首页 > 代码库 > 打击犯罪(black)
打击犯罪(black)
题目描述
某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了一个庞大的犯罪集团，犯罪集团的危险程度唯一由集团内的犯罪团伙数量确定，而与单个犯罪团伙的危险程度无关（该犯罪集团的危险程度为n）。现在当地警方希望花尽量少的时间（即打击掉尽量少的团伙），使得庞大的犯罪集团分离成若干个较小的集团，并且他们中最大的一个的危险程度不超过n/2。为达到最好的效果，他们将按顺序打击掉编号1到k的犯罪团伙，请编程求出k的最小值。
第一行一个正整数n。接下来的n行每行有若干个正整数，第一个整数表示该行除第一个外还有多少个整数，若第i行存在正整数k，表示i，k两个团伙可以直接联系。
一个正整数，为k的最小值
7
2 2 5
3 1 3 4
2 2 4
2 2 3
3 1 6 7
2 5 7
2 5 6
1
题目分析
方法一：
从第一个数开始 求出去掉这个数之后的危险程度
然后和 n/2 比较 如果说大于它 就继续删除下一个数字
（两个数字同时删除 求出最大危险程度）
知道最大危险程度小于 n/2 时 停止循环
错误：
如果第一次删除的数字不符合条件
做下一次循环之前 要进行一系列的归零操作
要把上一次循环用到的数组 变量内的数 全部清零
方法二：
二分 删除的数字越小 最大危险程度越大
反比关系 所以就能用二分法求
每一次循环都求出中间点所对应的最大危险程度
（中间点即删除mid和mid之前的所有的点 并非一个点）
求出mid所对应的危险程度 就和 n/2 比较
然后不断地缩小比较的范围 就能二分求出答案
错误：
二分的时候 不需要像邻接矩阵一样把查过的点都删除
因为如果删除了 下一次的查找范围如果在之前的话
就必须再重新构建矩阵 直接不用删除 在 k+1 个开始查找即可
这样 矩阵里面的数字没有变 也找到了mid对应的危险程度
源代码
方法一：
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
void dfs(int);
void find_group();
int n,x,m,y,u,w[1005][1005],group[1005],t,ans[1005],a,maxx,g;
bool vis[1005];
int main()
{
freopen("black3.in","r",stdin);
scanf("%d",&n);
m=n/2;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
for(int j=1;j<=x;j++)
{
scanf("%d",&y);
w[i][y]=1;
w[y][j]=w[j][y];
}
}
for(int k=1;k<=n;k++)
{
memset(group,0,sizeof(group));
memset(ans,0,sizeof(ans));
memset(vis,false,sizeof(vis));
maxx=0;
u=k;
for(int j=k+1;j<=n;j++)
if(w[k][j]==1)
{
w[k][j]=0;
w[j][k]=w[k][j];
}
find_group();
if(maxx>m)
continue;
else
{
a=k;
break;
}
}
printf("%d",a);
return 0;
}
void find_group()
{
g=0;
for(int i=u+1;i<=n;i++)
if(group[i]==0)
{
g++;
dfs(i);
maxx=max(maxx,ans[g]);
}
t=g;
}
void dfs(int q)
{
vis[q]=true;
group[q]=g;
ans[g]++;
for(int l=u+1;l<=n;l++)
if(vis[l]==false&&w[q][l]==1)
dfs(l);
}
方法二：
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
void dfs(int);
void find_group();
int n,x,m,y,u,w[1005][1005],group[1005],t,ans[1005],a,maxx,g;
bool vis[1005];
int main()
{
freopen("black3.in","r",stdin);
scanf("%d",&n);
m=n/2;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
for(int j=1;j<=x;j++)
{
scanf("%d",&y);
w[i][y]=1;
w[y][i]=w[j][i];
}
}
for(int k=1;k<=n;k++)
{
memset(group,0,sizeof(group));
memset(ans,0,sizeof(ans));
memset(vis,false,sizeof(vis));
maxx=0;
u=k;
for(int j=k+1;j<=n;j++)
if(w[k][j]==1)
{
w[k][j]=0;
w[j][k]=w[k][j];
}
find_group();
if(maxx>m)
continue;
else
{
a=k;
break;
}
}
printf("%d",a);
return 0;
}
void find_group()
{
g=0;
for(int i=u+1;i<=n;i++)
if(group[i]==0)
{
g++;
dfs(i);
maxx=max(maxx,ans[g]);
}
t=g;
}
void dfs(int q)
{
vis[q]=true;
group[q]=g;
ans[g]++;
for(int l=u+1;l<=n;l++)
if(vis[l]==false&&w[q][l]==1)
dfs(l);
}
打击犯罪(black)