阿里云服务器wordpress建站教程,融资网站建设重点,免费网站推荐货源,合肥定制网站建设公司problem
luogu-P5361
他的联系薄上有 nnn 位好友#xff0c;他们两两之间或者互相认识#xff0c;或者互相不认识。
小 Q 希望在周六办一个热闹的聚会#xff0c;再在周日办一个尴尬的聚会。
一场热闹度为 ppp 的聚会请来了任意多位好友#xff0c;对于每一位到场的好友…problem
luogu-P5361
他的联系薄上有 nnn 位好友他们两两之间或者互相认识或者互相不认识。
小 Q 希望在周六办一个热闹的聚会再在周日办一个尴尬的聚会。
一场热闹度为 ppp 的聚会请来了任意多位好友对于每一位到场的好友来说都有至少 ppp 位他认识的好友也参加了聚会且至少对于一位到场的好友来说现场恰好有 ppp 位他认识的好友一场尴尬度为 qqq 的聚会请来了恰好 qqq 位好友且他们两两互不认识。
两场聚会可能有重复的参与者联系薄上也有可能有某些好友同时缺席了两场聚会。
小 Q 喜欢周六聚会的热闹度 ppp 与周日聚会的尴尬度 qqq 之间满足⌊np1⌋≤q\left\lfloor \frac{n}{p1} \right\rfloor\le q⌊p1n⌋≤q 且 ⌊nq1⌋≤p\left\lfloor \frac{n}{q1} \right\rfloor \le p⌊q1n⌋≤p。
请帮助小 Q 找出一个可行的邀请方案。
solution
observation1:\text{observation1}:observation1: ⌊np1⌋≤q∧⌊nq1⌋≤p⇔(p1)(q1)≥n1\lfloor\frac{n}{p1}\rfloor\le q\wedge \lfloor\frac{n}{q1}\rfloor\le p\Leftrightarrow (p1)(q1)\ge n1⌊p1n⌋≤q∧⌊q1n⌋≤p⇔(p1)(q1)≥n1。
我们只需要分别最大化 p,qp,qp,q 即可。
看似是两个独立的部分实际上他们各自的构造方式是一样的原理。
热闹的聚会。即度数限制的图。
每次找出当前图中度数最小的点更新 ppp 的最大值。
并删掉这个点动态地改变与之相连的其余点的度数。
将弹出的编号桉顺序记录下来并记下最大值的位置。
位置以前的点则是不被选的。 尴尬的聚会。即独立集。 每次找出当前图中度数最小的且未被标记的点加入尴尬的聚会。 然后标记与之直接相连的所有点都不能参加聚会。
下面给出该构造的正确性证明
将每个点加入尴尬的聚会除去这个点本身最多会从图中删掉 ppp 个点。显然 q≥⌈np1⌉q\ge \lceil\frac{n}{p1}\rceilq≥⌈p1n⌉。
如果独立集的选点运行了 qqq 次第 iii 次删掉的点度数为 did_idi。
则有 ∑i1q(di1)≥n\sum_{i1}^q(d_i1)\ge n∑i1q(di1)≥n。而 (q1)⋅max(di1)≥n(q1)·\max(d_i1)\ge n(q1)⋅max(di1)≥n 显然。
code
#include bits/stdc.h
using namespace std;
#define maxn 10005
#define Pair pair int, int
int T, n, m;
int p[maxn], q[maxn], vis[maxn], deg[maxn], d[maxn];
vector int G[maxn];
priority_queue Pair, vector Pair , greater Pair Q;int main() {scanf( %d, T );while( T -- ) {scanf( %d %d, n, m );for( int i 1;i n;i ) deg[i] 0;for( int i 1;i n;i ) G[i].clear();for( int i 1, u, v;i m;i ) {scanf( %d %d, u, v );G[u].push_back( v );G[v].push_back( u );deg[u] , deg[v] ;}int ans1 0, cnt1 0, pos;for( int i 1;i n;i ) vis[i] 0;for( int i 1;i n;i ) d[i] deg[i];for( int i 1;i n;i ) Q.push( make_pair( d[i], i ) );while( ! Q.empty() ) {int u Q.top().second, w Q.top().first; Q.pop();if( vis[u] ) continue; vis[u] 1;p[ cnt1] u;if( w ans1 ) ans1 w, pos cnt1;for( int v : G[u] ) if( ! vis[v] ) Q.push( make_pair( --d[v], v ) );}int ans2 0, cnt2 0;for( int i 1;i n;i ) vis[i] 0;for( int i 1;i n;i ) d[i] deg[i];for( int i 1;i n;i ) Q.push( make_pair( d[i], i ) );while( ! Q.empty() ) {int u Q.top().second, w Q.top().first; Q.pop();if( vis[u] ) continue;vis[u] 1;q[ cnt2] u;for( int v : G[u] ) vis[v] 1;}for( int i 1;i n;i ) vis[i] 0;for( int i 1;i pos;i ) vis[p[i]] 1;printf( %d , n - pos );for( int i 1;i n;i ) if( ! vis[i] ) printf( %d , i );puts();printf( %d , cnt2 );for( int i 1;i cnt2;i ) printf( %d , q[i] );puts();}return 0;
}
