BZOJ1040: [ZJOI2008]骑士树套环DP

题意：一个图n个点n条边保证点能互相到达，ab有边意味着ab互相厌恶，求一个集合，使得集合里元素最多而且没有人互相厌恶
删去环上一条边树形dp，比如删掉的边连着a，b，那么先dp出不选a的最大值，再dp出不选b的最大值。
如果每次找到环删边的方法是直接把边断掉，这样会出现一个Bug就是a有指向b的边，b有指向a的边，这样形成的环其实不需要删掉
解决办法：就是建边的时候如果是上面的情况a b之间就建了两条边，那这样把重边删去就行了（删完之后就break掉）

代码：

 1 #include <bits/stdc++.h>
 2 #define nmax 1000010
 3   
 4 using namespace std;
 5 typedef long long ll;
 6 vector <int> g[nmax];
 7 int n, in, a, b, cnt;
 8 ll d[nmax][2]={0}; // dp[u][1] = sum dp[v][0] + zl[u]   dp[u][0] = sum max(dp[v][0],dp[v][1]+x[v]) 
 9 int zl[nmax], vis[nmax]={0};
10   
11 void dfs(int u, int fa){
12     d[u][1] = zl[u];
13     for (int i=0; i<g[u].size(); i++) {
14         int v = g[u][i];
15         if(v==fa || v==0) continue;
16         dfs(v, u);
17         d[u][1] += d[v][0];
18         d[u][0] += max(d[v][0], d[v][1]);
19     }
20 }
21   
22 void fr(int u, int fa){
23     cnt++;
24     vis[u] = 1;
25     for (int i=0; i<g[u].size(); i++) {
26         int v = g[u][i];
27         if(v == fa || v == 0) continue;
28         if( vis[v] ) { a=u; b=v; }
29         else fr(v, u);
30     }
31 }
32   
33 inline void del(int x, int y){
34     for (int i=0; i<g[x].size(); i++) if( g[x][i] == y ) { g[x][i] = 0; break; }
35 }
36   
37 inline void init(int u, int fa){
38     d[u][0] = d[u][1] = 0;
39     for (int i=0; i<g[u].size(); i++) {
40         int v = g[u][i];
41         if( v==fa || v==0 ) continue;
42         init(v, u);
43     }
44 }
45   
46 int main(){
47     cin >> n;
48     for (int i=1; i<=n; i++) {
49         scanf("%d%d", &zl[i], &in);
50         g[in].push_back(i);
51         g[i].push_back(in);
52     }
53     ll ans=0, ta;
54     for (int i=1; i<=n; i++) {
55         if(vis[i]) continue;
56         cnt = 0; //这个树套环的节点个数
57         fr(i, 0);
58         del(a, b);
59         del(b, a);
60         dfs(a, 0);
61         ta = d[a][0];
62         init(i, 0);
63         dfs(b, 0);
64         ta = max(ta, d[b][0] );
65         init(i, 0);
66         ans += ta;
67     }
68     cout << ans << endl;
69     return 0;
70 }

(⓿_⓿)

BZOJ1040: [ZJOI2008]骑士 树套环DP

BZOJ1040: [ZJOI2008]骑士树套环DP