LOJ3113
SOL
对于题目的
p
,
q
p,q
p,q的限制，我们可以转化成
(
p
+
1
)
(
q
+
1
)
>
n
(p+1)(q+1)\gt n
(p+1)(q+1)>n，q是求最大独立集，但是此题不是二分图，无法用网络流等方式。
我们需要最大化地求
p
,
q
p,q
p,q。
构造方法
先贪心地求出最大的
p
p
p。
不妨把“加点”的思路转化为“删点“,即已经有一个合法的图，我们考虑让它更大。删除度数最小的点，才可能增大答案。所以一路删点记录最大值的时刻，即为
p
p
p的最大值方案。
接下来构造合法的问题2方案。
我们思考如下做法：
现在原图中选出度数最小的点
P
P
P，删除，存入点集
S
S
S中，并将与
P
P
P相连的所有点一并删除，再更新剩下的点的度数。重复这一过程，直到删完所有点。
最后得到的点集
S
S
S即为方案二答案。
证明：
1.S对于问题二合法。 显然。
2.S集合的大小
q
q
q，满足
(
q
+
1
)
(
p
+
1
)
>
n
(q+1)(p+1)\gt n
(q+1)(p+1)>n
设
d
P
i
d_{P_i}
dPi表示
S
S
S集合中点
P
i
P_i
Pi度数。
n
=
∑
i
=
1
∣
S
∣
(
即
为
q
)
(
d
P
i
+
1
)
n=\sum_{i=1}^{|S|( 即为q)} (d_{P_i}+1)
n=∑i=1∣S∣(即为q)(dPi+1)
设
D
m
a
x
Dmax
Dmax为
d
P
i
d_{P_i}
dPi中的最大值，问题一中构造出的最大值为
p
p
p。 由于
p
p
p是最大的答案，故
p
≥
D
m
a
x
p\ge Dmax
p≥Dmax（否则
p
=
D
m
a
x
p=Dmax
p=Dmax）
(
p
+
1
)
∗
(
q
+
1
)
≥
(
D
m
a
x
+
1
)
∗
(
q
+
1
)
>
(
D
m
a
x
+
1
)
∗
q
≥
n
(p+1)*(q+1)\ge(Dmax+1)*(q+1)\gt (Dmax+1)*q\ge n
(p+1)∗(q+1)≥(Dmax+1)∗(q+1)>(Dmax+1)∗q≥n. 证毕。
总结
写一个set支持一下排序删点加点。
为了简化代码复杂度，我们可以直接做一遍2过程，取
p
=
D
m
a
x
p=Dmax
p=Dmax即可。
CODE
#include<bits/stdc++.h>
using namespace std
;
#define sf scanf
#define ri register int
#define in red()
#define gc getchar()
#define cs const
#define ll long long
inline int red(){
int num
=0,f
=1;char c
=gc
;
for(;!isdigit(c
);c
=gc
)if(c
=='-')f
=-1;
for(;isdigit(c
);c
=gc
)num
=(num
<<1)+(num
<<3)+(c
^48);
return num
*f
;
}
cs
int N
=1e4+10,M
=2e5+10;
int head
[N
],cnt
=1,nxt
[M
],to
[M
],d
[N
],n
,m
,top
,stk
[N
],dmx
,pos
,ban
[N
];
inline void adde(int u
,int v
){
++d
[u
];++d
[v
];
nxt
[++cnt
]=head
[u
];head
[u
]=cnt
;to
[cnt
]=v
;
nxt
[++cnt
]=head
[v
];head
[v
]=cnt
;to
[cnt
]=u
;
}
typedef pair
<int,int> pi
;
#define fi first
#define se second
set
<pi
> s
;
#define It set<pi>::iterator
vector
<int>del
;
inline void delet(int u
){
for(ri i
=head
[u
];i
;i
=nxt
[i
]){
int v
=to
[i
];
if(ban
[v
])continue;
s
.erase(pi(d
[v
],v
));
s
.insert(pi(--d
[v
],v
));
}
}
inline void solve(){
n
=in
;m
=in
;
memset(head
,0,(n
+1)*sizeof(int));
memset(d
,0,(n
+1)*sizeof(int));
memset(ban
,0,(n
+1)*sizeof(int));
cnt
=1;top
=0;dmx
=0;
del
.clear();
for(ri i
=1;i
<=m
;++i
)adde(in
,in
);
for(ri i
=1;i
<=n
;++i
)s
.insert(pi(d
[i
],i
));
while(s
.size()){
int u
=s
.begin()->se
;s
.erase(s
.begin());
if(d
[u
]>dmx
)dmx
=d
[u
],pos
=top
;
stk
[++top
]=u
;
del
.push_back(u
);
ban
[u
]=1;
for(ri i
=head
[u
];i
;i
=nxt
[i
]){
int v
=to
[i
];
if(ban
[v
])continue;
s
.erase(pi(d
[v
],v
));
stk
[++top
]=v
;
ban
[v
]=1;
delet(v
);
}
}
cout
<<n
-pos
;for(ri i
=pos
+1;i
<=n
;++i
)cout
<<' '<<stk
[i
];cout
<<'\n';
cout
<<del
.size();for(ri i
=del
.size()-1;i
>=0;--i
)cout
<<' '<<del
[i
];cout
<<'\n';
}
signed main(){
int T
=in
;
while(T
--)solve();
return 0;
}
