每日一水第33弹

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=74288#problem/A

给你一棵树,以及一些路径,求不相交的最多的路径数量。点可以相交,边不能重叠。

对于一个子树,可以求得最多选择了多少的路径,然后有一些路径只有一段在这个子树内,这里开一个vector记录一下哪些点还可以延伸上来。

现在就考虑这样一个问题,u有最多10个儿子,每个儿子都有一些还可以延伸上来的点集,最多能选择多少条从一个子树上来经过u,再到某一个子树去 的路径。显然,由于点数比较小,可以暴力建立一个这10个儿子之间的关系矩阵。然后求出一个最大匹配累加答案即可。

另外,假如对于某个v,假如u和 v延伸上来的某个点组成一条路径的话,肯定可以贪心直接选择这个路径了,即把v的vector清空,答案+1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1010;
const int MAXD = 10;
bool tree[N][N], graph[N][N];
int n;
vector<int> son[N], up[N];
int ret, dp[1 << MAXD], mp[1 << MAXD];
bool tmp[MAXD][MAXD];
void DP(int n)
{
	dp[0] = 0;
	for(int i = 1; i < (1 << n); i++) {
	        int j = mp[i&-i];
                dp[i] = dp[i - (1 << j)];
                if(i == (i & -i)) {
                        continue;
                }
                for(int k = j + 1; k < n; k++) if(i >> k & 1){
                        if(tmp[j][k])
                                dp[i] = max(dp[i], dp[i - (1<<j) - (1 << k)] + 1);
                }
        }
}
void dfs(int u, int f)
{
        vector<int> son;
        for(int v = 0; v < n; v++) {
                if(v != f && tree[u][v]) {
                        dfs(v, u);
                        son.push_back(v);
                }
        }
        for(int v : son) {
                for(int vv: up[v]) {
                        if(graph[u][vv]) {
                                ret++;
                                up[v].clear();
                                break;
                        }
                }
        }
        memset(tmp, false, sizeof(tmp));
        int sz = son.size();
        for(int i = 0; i < sz; i++) {
                for(int j = i + 1; j < sz; j++) {
                        for(int x : up[son[i]]) {
                                for(int y : up[son[j]]) {
                                        if(graph[x][y]) {
                                                tmp[i][j] = true;
                                        }
                                }
                        }
                }
        }
        DP(sz);
        ret += dp[(1<<sz)-1];
        up[u].clear(); up[u].push_back(u);
        for(int i = 0; i < sz; i++) {
                if(dp[(1 << sz) - 1] == dp[(1<<sz)-1-(1<<i)]) {
                        for(int v : up[son[i]]) {
                                up[u].push_back(v);
                        }
                } else {
                }
        }
}
int main()
{
        for(int i = 0; i < 10; i++) {
                mp[1 << i] = i;
        }
        int t, m, a , b;
        scanf("%d", &t);
        while(t--) {
                scanf("%d", &n);
                ret = 0;
                for(int i = 0; i < n; i++) {
                        for(int j = 0; j < n; j++) {
                                tree[i][j] = graph[i][j] = false;
                        }
                }
                for(int i = 1; i < n; i++) {
                        scanf("%d%d", &a, &b);
                        a--; b--;
                        tree[a][b] = tree[b][a] = true;
                }
                scanf("%d", &m);
                for(int i = 0; i < m; i++)  {
                        scanf("%d%d", &a, &b); 
                        a--; b--;
                        graph[a][b] = graph[b][a] = true;
                }
                dfs(0, -1);
                printf("%d\n", ret);
        }
        return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注