【题解】HNOI2009无归岛

　　这题真的是无语了，在哪个岛上根本就没有任何的用处……不过我是画了下图，感受到一定是仙人掌，并不会证。有谁会证的求解……

　　如果当做仙人掌来做确实十分的简单。只要像没有上司的舞会一样树形dp就好了，遇到环出现的时候把环遍历一遍单独求解，和小C的独立集完全是一样的做法。

#include <bits/stdc++.h>
using namespace std;
#define maxn 500000
#define int long long
#define INF 999999999
int n, m, cnp = 1;
int f[maxn][2], fa[maxn], val[maxn];
int ans, timer, dfn[maxn], low[maxn];

struct edge
{
    int cnp = 1, head[maxn], to[maxn], last[maxn];
    void add(int u, int v)
    {
        to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++;
        to[cnp] = u, last[cnp] = head[v], head[v] = cnp ++;
    }
}E1;

int read()
{
    int x = 0, k = 1;
    char c;
    c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

void Solve(int u, int v)
{
    bool flag = 0;
    if(u == 3) flag = 1;
    int f1 = 0, f0 = 0;
    for(int i = v; i != u; i = fa[i])
    {
        int t0 = f0 + f[i][0], t1 = f1 + f[i][1];
        f0 = max(t0, t1), f1 = t0;
    }
    f[u][0] += f0;
    f1 = -INF, f0 = 0;
    for(int i = v; i != u; i = fa[i])
    {
        int t0 = f[i][0] + f0, t1 = f[i][1] + f1;
        f1 = t0, f0 = max(t0, t1);
    }
    f[u][1] += f1;
}

void Tarjan(int u)
{
    dfn[u] = low[u] = ++ timer;
    f[u][0] = 0, f[u][1] = val[u];
    for(int i = E1.head[u]; i; i = E1.last[i])
    {
        int v = E1.to[i];
        if(v == fa[u]) continue;
        if(!dfn[v]) 
        {
            fa[v] = u; Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], dfn[v]);
        if(low[v] > dfn[u] && fa[v] == u) 
            f[u][1] += f[v][0], f[u][0] += max(f[v][0], f[v][1]);
    }
    for(int i = E1.head[u]; i; i = E1.last[i])
    {
        int v = E1.to[i];
        if(dfn[v] > dfn[u] && fa[v] != u) Solve(u, v);
    }
}

signed main()
{
    n = read(), m = read();
    for(int i = 1; i <= m; i ++)
    {
        int u = read(), v = read();
        E1.add(u, v);
    }
    for(int i = 1; i <= n; i ++)
        val[i] = read();
    for(int i = 1; i <= n; i ++)
    {
        if(dfn[i]) continue; 
        Tarjan(i); ans += max(f[i][1], f[i][0]);
    }
    printf("%lld
", ans);
    return 0;
}