bzoj 1040: [ZJOI2008]骑士

第一次做环套树的题

这道题题目中貌似是有向边，实际上想一想就知道是无向的。

因为一个骑士觉得另一个骑士丑他们俩就走不到一起。

所以整个图实际上是一个无向环套树森林。

对于每一棵环套树，先dfs找环，找到环以后断环为链并将断开的两个点强制其中一个点为根且不选做一次树形DP，对另一个点做同样操作。

取两次结果最大值加入ans

  1 /*
  2 ID:WULALA
  3 PROB:bzoj1040 
  4 LANG:C++
  5 */
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <algorithm>
  9 #include <cmath>
 10 #include <iostream>
 11 #include <fstream>
 12 #include <ctime>
 13 #define N 1000008
 14 #define M
 15 #define mod
 16 #define mid(l,r) ((l+r) >> 1)
 17 #define INF 0x7ffffff
 18 using namespace std;
 19 
 20 int dfn[N],que,n,g[N],f[N],u,v,w[N],r,tot,ans,head[N],fa[N];
 21 bool vis[N];
 22 
 23 struct WULALA
 24 {
 25     int node,next;
 26 }e[2*N];
 27 
 28 void add(int x,int y)
 29 {
 30     e[++tot].node = y;
 31     e[tot].next = head[x];
 32     head[x] = tot;
 33     e[++tot].node = x;
 34     e[tot].next = head[y];
 35     head[y] = tot;
 36 }
 37 
 38 void init()
 39 {
 40     scanf("%d",&n);
 41     for (int i = 1;i <= n;i++)
 42     {
 43         int b;
 44         scanf("%d%d",&w[i],&b);
 45         add(i,b);
 46     }
 47 }
 48 
 49 void find_cir(int a)
 50 {
 51     vis[a] = true;
 52     int c = head[a];
 53     while(c)
 54     {
 55         if (e[c].node == fa[a])
 56             {c = e[c].next; continue;}
 57         if (vis[e[c].node])
 58         {
 59             u = e[c].node;
 60             v = a;
 61         }
 62         else
 63         {
 64             fa[e[c].node] = a;
 65             find_cir(e[c].node);
 66         }
 67         c = e[c].next;
 68     }
 69 }
 70 
 71 int dfs(int a,int m)
 72 {
 73     if (m != v) f[a] = w[a];
 74     int c = head[a];
 75     while(c)
 76     {
 77         if (e[c].node == fa[a]||e[c].node == u)
 78         {c = e[c].next; continue;}
 79         fa[e[c].node] = a;
 80         dfs(e[c].node,m);
 81         g[a] += max(g[e[c].node],f[e[c].node]);
 82         f[a] += g[e[c].node];
 83         c = e[c].next;
 84     }
 85     if (a == u)
 86     {
 87         if (m == u) return g[u];
 88         return (max(g[u],f[u]));
 89     }
 90 }
 91 
 92 void work(int a)
 93 {
 94     int r; 
 95     memset(f,0,sizeof(f));
 96     memset(g,0,sizeof(g));
 97     memset(fa,0,sizeof(fa));
 98     find_cir(a);
 99     memset(fa,0,sizeof(fa)); 
100     memset(f,0,sizeof(f));
101     memset(g,0,sizeof(g));
102     fa[u] = v;
103     r = dfs(u,v);
104     memset(f,0,sizeof(f));
105     memset(g,0,sizeof(g));
106     r = max(r,dfs(u,u));
107     ans += r;
108 }
109 
110 int main()
111 {
112     init();
113     for (int i = 1;i <= n;i++)
114         if (!vis[i]) work(i);
115     printf("%d
",ans);
116     return 0;
117 }

View Code