【AHOI2013复仇】ZJOI2008 骑士 题解

Posted on 2012-09-01 17:03 Mato_No1 阅读(1007) 评论(0)  编辑 收藏 引用 所属分类: 经典问题的模型ZJOI
原题地址
本沙茶的第一个无向环套树模型,纪念一下……

环套树,指的是每个连通块中点数都等于边数的无向图(称为无向环套树)或者是每个点有且只有一个前趋(称为内向环套树)或后继(称为外向环套树)的有向图,由于这个图的每个连通块当中有且只有一个环(注意,可能是自环,即长度为1的环),且这个环上的每个点都可以当作根引出一棵树,所以叫“环套树”。

对于无向环套树,先将整个图进行一次DFS,当中如果发现有逆向边(这条边第一次被发现必然是作为逆向边的,也就是起点是终点的后代),就说明找到了这个环,记录其起点和终点(注意,如果有多个连通块的话,不能退出,要继续遍历完),再不断上溯(因此在DFS过程中当然要记录父边了囧),就可以找到整个环了,然后再以环上的结点为根建树即可,这样依次处理每个连通块。

对于内向环套树(外向类似),找环更为简单,只需要任选一个点,不断去找它的前趋,同时记录找到的点序列,直到某个点在序列中出现两次为止,此时这个点以及序列中它两次出现的位置中间的所有点,就是环上的点,顺序也顺便记录下来,然后树也不用建了,直接在原图中找就行了。

对于这题,由于每个点都有且只有一个后继,所以是外向环套树,不过本沙茶更倾向于它的基图(无向图,是无向环套树),然后就是一个DP了囧……

代码:
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 1000010;
const ll INF = ~0Ull >> 2;
struct edge {
    
int a, b, pre, next;
} E0[MAXN 
* 3], E[MAXN << 1];
int n, m0, m, A[MAXN], stk[MAXN], st[MAXN], pr[MAXN], Q[MAXN];
ll F[MAXN][
2], res = 0;
bool vst[MAXN], vst0[MAXN];
void init_d()
{
    re(i, n) E0[i].pre 
= E0[i].next = E[i].pre = E[i].next = i; if (n & 1) m0 = n + 1else m0 = n; m = n;
}
void add_edge0(int a, int b)
{
    E0[m0].a 
= a; E0[m0].b = b; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
    E0[m0].a 
= b; E0[m0].b = a; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void add_edge(int a, int b)
{
    E[m].a 
= a; E[m].b = b; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void init()
{
    scanf(
"%d"&n); int x; init_d();
    re(i, n) {
        scanf(
"%d%d"&A[i], &x); add_edge0(--x, i);
    }
}
void sol0(int x)
{
    Q[
0= x; int i, j, front, rear;
    
for (front=0, rear=0; front<=rear; front++) {
        i 
= Q[front];
        
for (int p=E0[i].next; p != i; p=E0[p].next) {
            j 
= E0[p].b;
            
if (!vst0[j]) {Q[++rear] = j; vst0[j] = 1; add_edge(i, j);}
        }
    }
    rre3(z, rear, 
0) {
        i 
= Q[z];
        F[i][
0= 0; F[i][1= A[i];
        
for (int p=E[i].next; p != i; p=E[p].next) {
            j 
= E[p].b; F[i][0+= F[j][0>= F[j][1? F[j][0] : F[j][1]; F[i][1+= F[j][0];
        }
    }
}
void solve()
{
    re(i, n) {vst[i] 
= vst0[i] = 0; st[i] = E0[i].next;} int x, y, tp, x0, y0; bool FF, FF2; ll tmp0, tmp1, tmp00, tmp01, res0;
    re(i, n) 
if (!vst[i]) {
        stk[tp 
= 0= i; vst[i] = 1; FF2 = 0;
        
while (tp >= 0) {
            x 
= stk[tp]; FF = 0;
            
for (int p=st[x]; p != x; p=E0[p].next) {
                y 
= E0[p].b;
                
if (!vst[y]) {vst[y] = 1; stk[++tp] = y; pr[y] = p; st[x] = E0[p].next; FF = 1break;}
                
else if (p != (pr[x] ^ 1&& !FF2) {FF2 = 1; x0 = x; y0 = y;}
            }
            
if (!FF) tp--;
        }
        
if (FF2) {
            tp 
= 0; vst0[y0] = 1while (x0 != y0) {stk[tp++= x0; vst0[x0] = 1; x0 = E0[pr[x0]].a;} stk[tp++= y0;
            re(j, tp) sol0(stk[j]);
            tmp0 
= F[stk[0]][0]; tmp1 = -INF;
            re2(j, 
1, tp) {
                tmp00 
= (tmp0 >= tmp1 ? tmp0 : tmp1) + F[stk[j]][0];
                tmp01 
= tmp0 + F[stk[j]][1];
                tmp0 
= tmp00; tmp1 = tmp01;
            }
            res0 
= tmp0 >= tmp1 ? tmp0 : tmp1;
            tmp0 
= -INF; tmp1 = F[stk[0]][1];
            re2(j, 
1, tp) {
                tmp00 
= (tmp0 >= tmp1 ? tmp0 : tmp1) + F[stk[j]][0];
                tmp01 
= tmp0 + F[stk[j]][1];
                tmp0 
= tmp00; tmp1 = tmp01;
            }
            res 
+= res0 >= tmp0 ? res0 : tmp0;
        }
    }
}
void pri()
{
    cout 
<< res << endl;
}
int main()
{
    init();
    solve();
    pri();
    
return 0;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理