菜啊，不会做，但是 wyz 讲的真好
简述题意：给定一张无向无权图，要求找到一张子图，使得子图上的所有点的度数 >= p，再找到一个子图，使得这张子图上的所有点都互相没有直接连边，点数为 q。要求： $\lfloor \frac{n}{p+1} \rfloor \leq q$ 且 $\lfloor \frac{n}{q+1} \rfloor \leq p$，输出任意一种符合条件的方案数
数据范围：$n\leq 10^4, m\leq 10^5$
这题分为两部分，自然做法也分两部分来考虑，先考虑 p 部分
wyz：二分题做多了一眼就能看出是二分
我们不断二分 p ，然后 check 一下能不能构造出满足当前条件的子图，这样找到一个最小的 p
因为第一部分和第二部分是相互独立的，又有 $\lfloor \frac{n}{p+1} \rfloor \leq q$，显然 p 越小的时候留给 q 的空间越大，越便于后面第二部分的解决
复杂度：$\Theta (nlogn)$
考虑第二部分
这不是 NPC 问题 最大团 嘛？？？？？？？？？？？？？？？？？？？
显然无法直接做，因为只需要找到一个满足条件的方案，考虑随机化（
我们可以每次随机一个排列，表示处理点的顺序，每次 $\Theta (n+m)$ 的检测是否可行
复杂度：$\Theta (玄学)$
但是实际上随机方法成功率极其高，几乎随机一次就可以找到答案
此外 wyz 还想到一个不完全正确的 $\Theta (n)$ 贪心，但是我不会
代码：
1 // #3113. 「SDOI2019」热闹的聚会与尴尬的聚会 2 3 #include <ctime> 4 #include <cmath> 5 #include <cstdio> 6 #include <cstring> 7 #include <cstdlib> 8 #include <iostream> 9 #include <algorithm> 10 #include <iterator> 11 #include <vector> 12 #include <queue> 13 #include <bitset> 14 #define inf 100010 15 #define INF 0x7fffffff 16 #define ll long long 17 18 namespace chiaro{ 19 20 namespace io { 21 const int SIZE = (1 << 21) + 1; 22 char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr; 23 24 #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++) 25 26 inline void flush () { 27 fwrite (obuf, 1, oS - obuf, stdout); 28 oS = obuf; 29 } 30 31 inline void putc (char x) { 32 *oS ++ = x; 33 if (oS == oT) flush (); 34 } 35 36 template <class I> 37 inline void read (I &x) { 38 for (f = 1, c = gc(); c < ‘0‘ || c > ‘9‘; c = gc()) if (c == ‘-‘) f = -1; 39 for (x = 0; c <= ‘9‘ && c >= ‘0‘; c = gc()) x = x * 10 + (c & 15); 40 x *= f; 41 } 42 43 template <class I> 44 inline void print (I x) { 45 if (!x) putc (‘0‘); 46 if (x < 0) putc (‘-‘), x = -x; 47 while (x) qu[++ qr] = x % 10 + ‘0‘, x /= 10; 48 while (qr) putc (qu[qr --]); 49 } 50 51 struct Flusher_ {~Flusher_(){flush();}}io_flusher_; 52 } 53 using io :: read; using io :: putc; using io :: print; 54 template <class T> 55 inline void read(T& a, T& b) {read(a); read(b);} 56 57 struct edge { 58 int to; 59 edge* next; 60 }; 61 62 int n, m; 63 int deg[inf]; 64 bool vis[inf]; 65 edge* g[inf << 6]; 66 67 inline void connect(int from, int to) { 68 static edge pool[inf << 6]; 69 static edge* p = pool; 70 p->to = to; 71 p->next = g[from]; 72 g[from] = p; p++; 73 return; 74 } 75 76 inline void clear() { 77 memset(g, 0, sizeof g); 78 memset(deg, 0, sizeof deg); 79 } 80 81 inline void Init() { 82 clear(); 83 read(n, m); 84 for(int i = 1; i <= m; i++) { 85 int u, v; read(u, v); 86 connect(u, v); 87 connect(v, u); 88 ++deg[u], ++deg[v]; 89 } 90 return; 91 } 92 93 namespace part1 { 94 int nowdeg[inf]; 95 int ans; 96 97 void del(int x, int p) { 98 vis[x] = 1; 99 for(edge* e = g[x]; e; e = e->next) { 100 int y = e->to; 101 if(vis[y]) continue; 102 --nowdeg[y]; 103 if(nowdeg[y] < p) del(y, p); 104 } 105 return; 106 } 107 108 inline void work(int p) { 109 memset(vis, 0, sizeof vis); 110 memcpy(nowdeg, deg, sizeof deg); 111 for(int i = 1; i <= n; i++) { 112 if(vis[i] == 0 && nowdeg[i] < p) del(i, p); 113 } 114 } 115 116 inline bool check(int p) { 117 work(p); 118 for(int i = 1; i <= n; i++) { 119 if(vis[i] == 0) return 1; 120 } 121 return 0; 122 } 123 124 inline void solve() { 125 int l, r, mid; 126 l = 0, r = n; 127 while(l < r) { 128 mid = l + ((r - l + 1) >> 1); 129 if(check(mid)) l = mid; 130 else r = mid - 1; 131 } 132 work(r); 133 ans = 0; 134 for(int i = 1; i <= n; i++) ans += (vis[i] == 0); 135 printf("%d ", ans); 136 for(int i = 1; i <= n; i++) { 137 if(vis[i] == 0) printf("%d ", i); 138 } 139 puts(""); 140 return; 141 } 142 } 143 144 namespace part2 { 145 int id[inf]; 146 147 inline void solve() { 148 srand(time(0)); 149 while(1) { 150 for(int i = 1; i <= n; i++) id[i] = i; 151 std::random_shuffle(id + 1, id + 1 + n); 152 memset(vis, 0, sizeof vis); 153 for(int i = 1; i <= n; i++) { 154 bool flag = 1; 155 for(edge* e = g[id[i]]; e; e = e->next) { 156 int to = e->to; 157 if(vis[to]) {flag = 0; break;} 158 } 159 if(flag) vis[id[i]] = 1; 160 } 161 int ans = 0; 162 for(int i = 1; i <= n; i++) ans += vis[i]; 163 if(ans < (n / (part1::ans + 1))) continue; 164 printf("%d ", ans); 165 for(int i = 1; i <= n; i++) { 166 if(vis[i]) printf("%d ", i); 167 } 168 puts(""); 169 return; 170 } 171 } 172 } 173 174 inline void setting(){ 175 #ifndef ONLINE_JUDGE 176 freopen("_test.in", "r", stdin); 177 freopen("_test.out", "w", stdout); 178 #endif 179 return; 180 } 181 182 inline int main() { 183 setting(); 184 int T; read(T); 185 while(T--) { 186 Init(); 187 part1::solve(); 188 part2::solve(); 189 } 190 return 0; 191 } 192 193 } 194 195 signed main(){ return chiaro::main();}
原文：https://www.cnblogs.com/Chiaro/p/problem-renaodejuhui.html
