UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213580#2769. 覆盖laiyishi30133ms1236kbC++11933b2024-11-12 21:13:112024-11-12 23:46:19

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,vis[25];
vector<int>g[25];
int r[25];
int dfs(int pos,int u,int vv,int fa){
	if(vv==u){
		r[pos]|=(1<<(vv-1));
		return 1;
	}
	vis[u]=1;
	for(int v:g[u]){
		if(vis[v])continue;
		if(dfs(pos,v,vv,u)){
			r[pos]|=(1<<(u-1));
			return 1;
		}
	}
	return 0;
}
int popc(int x){
	int ret=0;
	for(;x;x-=x&-x)ret++;
	return ret;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		memset(vis,0,sizeof(vis));
		dfs(i,u,v,-1);
	}
	int d=(1<<n)-1;
	for(int i=0;i<(1<<n);i++){
		int fl=1;
		for(int j=1;j<=m;j++){
			fl&=((r[j]&i)!=0);
		}
		if(fl){
			if(popc(d)>popc(i))d=i;
		}
	}
	printf("%d\n",popc(d));
	for(int i=1;i<=n;i++){
		if(d&(1<<(i-1)))printf("%d ",i);
	}
	printf("\n");
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 11ms
memory: 1236kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 13
17 15
18 16
19 17
20 18
...

output:

2
3 10 

result:

ok ok

Test #2:

score: 0
Accepted
time: 17ms
memory: 1236kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
...

output:

2
6 13 

result:

ok ok

Test #3:

score: 0
Accepted
time: 9ms
memory: 1236kb

input:

20
2 1
3 1
4 3
5 1
6 5
7 4
8 7
9 8
10 9
11 10
12 6
13 2
14 7
15 14
16 11
17 12
18 17
19 7
20 15
5
4 ...

output:

3
1 4 11 

result:

ok ok

Test #4:

score: 0
Accepted
time: 18ms
memory: 1236kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
...

output:

2
5 11 

result:

ok ok

Test #5:

score: 0
Accepted
time: 16ms
memory: 1236kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 6
10 8
11 10
12 11
13 11
14 12
15 13
16 9
17 15
18 16
19 16
20 17
1...

output:

6
1 3 7 10 17 19 

result:

ok ok

Test #6:

score: 0
Accepted
time: 13ms
memory: 1236kb

input:

20
2 1
3 2
4 3
5 3
6 5
7 4
8 6
9 8
10 7
11 7
12 10
13 12
14 13
15 9
16 14
17 16
18 16
19 17
20 15
12...

output:

3
4 9 13 

result:

ok ok

Test #7:

score: 0
Accepted
time: 8ms
memory: 1236kb

input:

20
2 1
3 1
4 2
5 3
6 4
7 5
8 6
9 7
10 8
11 9
12 10
13 11
14 10
15 14
16 10
17 13
18 4
19 18
20 4
2
1...

output:

2
5 8 

result:

ok ok

Test #8:

score: 0
Accepted
time: 10ms
memory: 1232kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 4
8 7
9 6
10 9
11 8
12 11
13 10
14 10
15 12
16 14
17 13
18 17
19 14
20 18
4...

output:

2
4 10 

result:

ok ok

Test #9:

score: 0
Accepted
time: 15ms
memory: 1236kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 8
12 10
13 12
14 8
15 13
16 8
17 8
18 16
19 15
20 11
12
8...

output:

3
3 8 10 

result:

ok ok

Test #10:

score: 0
Accepted
time: 16ms
memory: 1232kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 7
10 9
11 10
12 8
13 11
14 12
15 13
16 14
17 15
18 16
19 18
20 19
1...

output:

2
7 12 

result:

ok ok

Subtask #2:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

input:

1000
2 1
3 2
4 3
5 4
6 3
7 6
8 7
9 8
10 9
11 10
12 5
13 11
14 13
15 14
16 15
17 12
18 16
19 18
20 19...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #21:

score: 0
Runtime Error

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 11
15 14
16 13
17 15
18 16
19 17
2...

output:


result: