苏州做商城网站,宝安网站建设zrare,网站没有备案怎么做支付,网络营销推广引流方法打击犯罪
题目大意#xff1a;
有n个人#xff0c;相互之间有一些关系#xff0c;从而形成一个图#xff0c;现在要从1……n1……n1……n按顺序去掉k个人#xff08;即去掉1……k1……k1……k#xff09;#xff0c;使最大的子图的点数 n/2n/2n/2#xf…打击犯罪
题目大意
有n个人相互之间有一些关系从而形成一个图现在要从1……n1……n1……n按顺序去掉k个人即去掉1……k1……k1……k使最大的子图的点数 n/2n/2n/2求k的最小值
原题
题目描述
某个地区有n(n1000)个犯罪团伙当地警方按照他们的危险程度由高到低给他们编号为1-n他们有些团伙之间有直接联系但是任意两个团伙都可以通过直接或间接的方式联系这样这里就形成了一个庞大的犯罪集团犯罪集团的危险程度唯一由集团内的犯罪团伙数量确定而与单个犯罪团伙的危险程度无关该犯罪集团的危险程度为n。现在当地警方希望花尽量少的时间即打击掉尽量少的团伙使得庞大的犯罪集团分离成若干个较小的集团并且他们中最大的一个的危险程度不超过n/2。为达到最好的效果他们将按顺序打击掉编号1到k的犯罪团伙请编程求出k的最小值。
如下图所示打击掉1号团伙便能达到目的。
输入
第一行一个正整数n。 接下来的n行每行有若干个正整数第一个整数表示该行除第一个外还有多少个整数若第i行存在正整数k表示ik两个团伙可以直接联系。
输出
一个正整数为k的最小值
输入样例 72 2 53 1 3 42 2 42 2 33 1 6 72 5 72 5 6输出样例
1解题思路
因为要按顺序所以我们倒着用并查集加入每一个点然后看每一个子图是否符合当全部符合时继续否则就输出
代码
#includecstdio
#includecstring
#includeiostream
#define max(a,b) (a)(b)?(a):(b)
#define min(a,b) (a)(b)?(a):(b)
using namespace std;
int n,xx,yy,k,a[1005][1005],dad[1005],b[1005];
int find(int dep){return dad[dep]dep?dep:dad[dep]find(dad[dep]);}//并查集
void lj(int x,int y)
{xxfind(x);yyfind(y);dad[min(xx,yy)]max(xx,yy);//连接两个点
}
int main()
{scanf(%d,n);for (int i1;in;i){scanf(%d,a[i][0]);for (int j1;ja[i][0];j)scanf(%d,a[i][j]);}for (int i1;in;i)dad[i]i;int in1;while (!k){i--;for (int j1;ja[i][0];j)if (a[i][j]i) lj(i,a[i][j]);//插入点memset(b,0,sizeof(b));for (int ji;jn;j)b[find(j)];//累加for (int ji;jn;j){if (b[j]n/2)//判断{k1;//不符合break;}}}printf(%d,i);
}
