You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
188 lines
4.7 KiB
188 lines
4.7 KiB
2 years ago
|
# $Aimai$ $Trip$
|
||
|
|
|
||
|
|
### 题目描述
|
||
|
|
有 $n$ 只猫猫在玩捉迷藏。猫猫们的编号分别为 $1,2,\cdots,n$。
|
||
|
|
|
||
|
|
屋子里有 $k$ 个房间，**每个房间只能容纳一只猫猫**。
|
||
|
|
|
||
|
|
每个房间有一定的属性，可以用 $x_i,y_i$ 来表示，意为：
|
||
|
|
|
||
|
|
* 这个房间要么空着，要么容纳第 $x_i$ 只猫猫，要么容纳第 $y_i$ 只猫猫。
|
||
|
|
|
||
|
|
现在云浅可以买下前 $m$ 个房间给猫猫们使用。云浅想要知道，$m$ 的值至少是多少，才能容纳所有猫猫。**保证买下所有房间后一定可以容纳所有猫猫。**
|
||
|
|
|
||
|
|
为了更好地帮助小可爱，你还需要输出一个方案。如果有多个可行的方案，输出任意一个即可。
|
||
|
|
|
||
|
|
### 输入格式
|
||
|
|
|
||
|
|
第一行两个正整数 $n,k$。
|
||
|
|
|
||
|
|
第二行 $k$ 个正整数 $x_1,\cdots,x_k$，表示每个房间的第一种属性。
|
||
|
|
|
||
|
|
第三行 $k$ 个正整数 $y_1,\cdots,y_k$，表示每个房间的第二种属性。
|
||
|
|
|
||
|
|
### 输出格式
|
||
|
|
|
||
|
|
先输出一行一个正整数 $m$ 表示答案。
|
||
|
|
|
||
|
|
第二行输出 $m$ 个正整数，以空格隔开。其中，若第 $i$ 个数为 $0$ 则表示第 $i$ 个房间空着不用，第 $i$ 个数为 $1$ 则表示分给第 $x_i$ 只猫猫，第 $i$ 个数为 $2$ 则表示分给第 $y_i$ 只猫猫。
|
||
|
|
|
||
|
|
### 数据范围
|
||
|
|
|
||
|
|
对于 $100\%$ 的数据，$1\le n \le 10^5,1\le k\le 2\times 10^5,1\le x_i,y_i\le n,x_i\neq y_i$。
|
||
|
|
|
||
|
|
| 测试点编号 | $n$ | $k$ |
|
||
|
|
| :---------: | :--------: | :----------------: |
|
||
|
|
| $1\sim 6$ | $\le 20$ | $\le 20$ |
|
||
|
|
| $7\sim 10$ | $\le 1000$ | $\le 1000$ |
|
||
|
|
| $11\sim 14$ | $\le 1000$ | $\le 10^5$ |
|
||
|
|
| $15\sim 20$ | $\le 10^5$ | $\le 2\times 10^5$ |
|
||
|
|
|
||
|
|
<div style="page-break-after: always"></div>
|
||
|
|
|
||
|
|
### 题解
|
||
|
|
首先二分答案，相当于只需要判定一下是否所有小可爱都能住进至少一个房间。
|
||
|
|
|
||
|
|
考虑对每个房间连边 $(x_i,y_i)$，那么，所有小可爱都能住进至少一个房间，当且仅当：
|
||
|
|
|
||
|
|
* 图中的每个连通块的边数均不小于点数。
|
||
|
|
|
||
|
|
证明：若要求所有小可爱都能住进至少一个房间，显然边数必然不小于点数。
|
||
|
|
|
||
|
|
如果边数不小于点数，那么这个连通块中至少存在一个环。考虑令在环上的边所代表的房间依次给第 $x_i$ 只小可爱，然后从这个环向外延伸出去若干条链，链上的边从环内指向环外即可。
|
||
|
|
|
||
|
|
构造方案也可以使用类似的方法。
|
||
|
|
|
||
|
|
于是就做完了，时间复杂度 $O((n+k)\log k)$。
|
||
|
|
|
||
|
|
|
||
|
|
#### 参考代码
|
||
|
|
|
||
|
|
```c++{.line-numbers}
|
||
|
|
#include<bits/stdc++.h>
|
||
|
|
|
||
|
|
#define int long long
|
||
|
|
|
||
|
|
using namespace std;
|
||
|
|
|
||
|
|
inline int read(){
|
||
|
|
int x=0,f=1;char c=getchar();
|
||
|
|
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
|
||
|
|
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
|
||
|
|
return x*f;
|
||
|
|
}
|
||
|
|
|
||
|
|
const int MN=2e5+5;
|
||
|
|
int n,k;
|
||
|
|
int fr[MN],to[MN];
|
||
|
|
|
||
|
|
struct Edge{
|
||
|
|
int to,id;
|
||
|
|
Edge(int T,int I):to(T),id(I){}
|
||
|
|
Edge(){}
|
||
|
|
};
|
||
|
|
|
||
|
|
vector<Edge>G[MN];
|
||
|
|
vector<int>S;
|
||
|
|
bool vis[MN];
|
||
|
|
|
||
|
|
void getnodes(int u){
|
||
|
|
vis[u]=1;S.push_back(u);
|
||
|
|
for(auto e:G[u]){
|
||
|
|
int v=e.to,i=e.id;
|
||
|
|
if(!vis[v])getnodes(v);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
vector<int>C;
|
||
|
|
int fa[MN],pre[MN],res[MN];
|
||
|
|
bool fi=0;
|
||
|
|
void findcycle(int u){
|
||
|
|
vis[u]=1;
|
||
|
|
for(auto e:G[u]){
|
||
|
|
int v=e.to,i=e.id;
|
||
|
|
if(i==pre[u])continue;
|
||
|
|
if(!vis[v]){fa[v]=u,pre[v]=i,findcycle(v);continue;}
|
||
|
|
if(fi)continue;
|
||
|
|
int x=u;
|
||
|
|
while(x!=v){
|
||
|
|
C.push_back(x),res[pre[x]]=(fr[pre[x]]==x?2:1);
|
||
|
|
x=fa[x];
|
||
|
|
}
|
||
|
|
res[i]=(fr[i]==u?1:2);fi=1;C.push_back(v);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
bool chk(int m){
|
||
|
|
for(int i=1;i<=n;i++)G[i].clear();
|
||
|
|
memset(vis,0,sizeof(vis)),memset(pre,0,sizeof(pre)),memset(fa,0,sizeof(fa));
|
||
|
|
|
||
|
|
for(int i=1;i<=m;i++){
|
||
|
|
int u=fr[i],v=to[i];
|
||
|
|
G[u].push_back(Edge(v,i)),G[v].push_back(Edge(u,i));
|
||
|
|
}
|
||
|
|
|
||
|
|
for(int i=1;i<=n;i++){
|
||
|
|
if(vis[i])continue;
|
||
|
|
fi=0,C.clear();findcycle(i);
|
||
|
|
if(!fi)return 0;
|
||
|
|
}
|
||
|
|
return 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
void dfs(int u){
|
||
|
|
vis[u]=1;
|
||
|
|
for(auto e:G[u]){
|
||
|
|
int v=e.to,i=e.id;
|
||
|
|
if(vis[v]||res[i]!=0)continue;
|
||
|
|
res[i]=(fr[i]==v?1:2);dfs(v);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void getans(int m){
|
||
|
|
for(int i=1;i<=n;i++)G[i].clear();
|
||
|
|
memset(vis,0,sizeof(vis)),memset(pre,0,sizeof(pre));
|
||
|
|
memset(fa,0,sizeof(fa)),memset(res,0,sizeof(res));
|
||
|
|
|
||
|
|
for(int i=1;i<=m;i++){
|
||
|
|
int u=fr[i],v=to[i];
|
||
|
|
G[u].push_back(Edge(v,i)),G[v].push_back(Edge(u,i));
|
||
|
|
}
|
||
|
|
|
||
|
|
for(int i=1;i<=n;i++){
|
||
|
|
if(vis[i])continue;
|
||
|
|
S.clear();getnodes(i);fi=0;
|
||
|
|
for(int p:S)vis[p]=0;
|
||
|
|
C.clear();findcycle(i);
|
||
|
|
for(int p:S)vis[p]=0;
|
||
|
|
for(int p:C)vis[p]=1;
|
||
|
|
for(int p:C)dfs(p);
|
||
|
|
for(int p:S)vis[p]=1;
|
||
|
|
}
|
||
|
|
|
||
|
|
for(int i=1;i<=m;i++)cout<<res[i]<<" ";puts("");
|
||
|
|
}
|
||
|
|
|
||
|
|
signed main(void){
|
||
|
|
|
||
|
|
freopen("cats.in","r",stdin);
|
||
|
|
freopen("cats.out","w",stdout);
|
||
|
|
|
||
|
|
n=read(),k=read();
|
||
|
|
for(int i=1;i<=k;i++)fr[i]=read();
|
||
|
|
for(int i=1;i<=k;i++)to[i]=read();
|
||
|
|
int L=1,R=k,ans=L;
|
||
|
|
while(L<=R){
|
||
|
|
int mid=(L+R)>>1;
|
||
|
|
if(chk(mid))R=mid-1,ans=mid;
|
||
|
|
else L=mid+1;
|
||
|
|
}
|
||
|
|
cout<<ans<<endl;
|
||
|
|
getans(ans);
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
```
|
||
|
|
|
||
|
|
<div style="page-break-after: always"></div>
|