bzoj2530 [POI2011]Party

骑猪看日落 2021-11-29 12:16 386阅读 0赞

[bzoj2530 \[POI2011\]Party][bzoj2530 _POI2011_Party]

> 给定一张 \\(n\\) （保证 \\(n\\) 是 \\(3\\) 的倍数）个节点 \\(m\\) 条边的图，并且保证该图存在一个大小至少为 \\(\\frac\{2\}\{3\}n\\) 的团。请输出该图的任意一个大小为 \\(\\frac\{1\}\{3\}n\\)的团。
> 
> \\(n\\leq3000,\\ m\\leq n^2\\)

贪心

--------------------

神仙题一道……

结论：把所有不相邻的节点判掉，输出剩下的节点

若两点都不在团中，显然直接判掉；若其中一点在团中，判掉会失去一个答案节点。由于有至少 \\(\\frac\{2\}\{3\}n\\) 个点两两相邻，因此最多只会执行 \\(\\frac\{1\}\{3\}n\\) 次判点操作，于是就至少会留下 \\(\\frac\{1\}\{3\}n\\) 个点，输出即可

时间复杂度 \\(O(n^2)\\)

代码

#include <bits/stdc++.h> using namespace std; const int maxn = 3010; int n, m, flg[maxn], a[maxn][maxn]; int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); a[u][v] = a[v][u] = 1; } for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n && !flg[i]; j++) { if (!a[i][j] && !flg[j]) { flg[i] = flg[j] = 1; } } } int cnt = 0; for (int i = 1; i <= n; i++) { if (!flg[i]) { if (++cnt > n / 3) break; printf("%d ", i); } } return 0; }

转载于:https://www.cnblogs.com/Juanzhang/p/10883748.html

[bzoj2530 _POI2011_Party]: https://www.lydsy.com/JudgeOnline/problem.php?id=2530

发表评论取消回复

表情：

评论列表（有 0 条评论，386人围观）

还没有评论，来说两句吧...

相关阅读

相关 @bzoj - 3836@ [Poi2014]Tourism

目录 @description@ @solution@ @accepted code@ @details@ --------------------

客官°小女子只卖身不卖艺/ 2023年06月01日 13:58/ 0 赞/ 134 阅读

相关 BZOJ2527[Poi2011]Meteors——整体二分+树状数组

题目描述 Byteotian Interstellar Union (BIU) has recently discovered a new planet in a nea

冷不防/ 2022年01月13日 04:19/ 0 赞/ 167 阅读

相关 bzoj 2763: [JLOI2011]飞行路线

1 include<cstdio> 2 include<cstring> 3 include<iostream> 4 include<qu

绝地灬酷狼/ 2022年01月10日 19:55/ 0 赞/ 155 阅读

相关 BZOJ2242[SDOI2011]计算器——exgcd+BSGS

题目描述你被要求设计一个计算器完成以下三项任务： 1、给定y,z,p,计算Y^Z Mod P 的值； 2、给定y,z,p，计算满足xy≡ Z ( mod P )的最

约定不等于承诺〃/ 2022年01月05日 15:15/ 0 赞/ 197 阅读

相关 bzoj2530 [POI2011]Party

[bzoj2530 \[POI2011\]Party][bzoj2530 _POI2011_Party] > 给定一张 \\(n\\) （保证 \\(n\\) 是 \\(3\

骑猪看日落/ 2021年11月29日 12:16/ 0 赞/ 387 阅读

相关 [POI2011]DYN-Dynamite

[题面][Link 1] 题意:给一棵树,树上有一些关键节点,选m个点,使得关键节点到这些点中距离的最小值的最大值最小最大值最小,果断二分答案我们只需要判定是否存在m

川长思鸟来/ 2021年11月13日 15:14/ 0 赞/ 119 阅读

相关 [bzoj2242] [SDOI2011]计算器

\570. \[bzoj2242\] \[SDOI2011\]计算器题目描述你被要求设计一个计算器完成以下三项任务： 1、给定y,z,p,计算Y^Z Mod

清疚/ 2021年10月29日 07:18/ 0 赞/ 241 阅读

相关 bzoj2462: [BeiJing2011]矩阵模板

[咕咕咕][Link 1] 这题数据有点水...我直接求矩阵和，比较矩阵大小...还a了矩阵hash棵题 ![1542296-20190809093429027-

我就是我/ 2021年10月26日 13:31/ 0 赞/ 179 阅读

相关【HNOI2011/bzoj2337】XOR和路径

第二道高斯消元练习题 -------------------- 题意一张无向图，从点 $1$ 出发每次随机选一条出边走，走到 $n$ 停止，求经过的所有边权异或和的

野性酷女/ 2021年09月30日 12:44/ 0 赞/ 194 阅读

相关 BZOJ2242：[SDOI2011]计算器——题解

[https://www.lydsy.com/JudgeOnline/problem.php?id=2242][https_www.lydsy.com_JudgeOnline_

灰太狼/ 2021年09月20日 09:36/ 0 赞/ 221 阅读