https://www.lydsy.com/JudgeOnline/problem.php?id=4316
题意:给出一张仙人掌图,求最大独立集。
首先,对于一棵树,我们知道它的最大独立集可以dp求出。
f[i][0/1] 表示 不选/选 结点 i。
{f[u][0]=∑(u,v)∈Emax(f[v][1],f[v][0])f[u][1]=∑(u,v)∈Ef[v][1]
然而本题有环,环上两点的最大独立集显然无法这样求出,但若只有一个点属于环,则仍然存在父子之间的dp关系。所以考虑把环单独拿出来考虑。
圆圆点之间的连边与树边相同,而方点表示一个环,所以单独考虑。
方点的 f 值表示与环的最高点(dfs序最小的点)相邻的两个点取或不取。当遇到方点,则把环提取出来,由于栈顶和底之间隔着环的父亲,所以直接单向dp。
由于圆方树是有向树,所以方点的父亲,即环的最高点,此时可以直接利用方点进行转移。
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
| #include<bits/stdc++.h> using namespace std; #define ll long long const int INF = 0x3f3f3f3f; const int maxn = 100003; int n, m, nn; vector<int>gg[maxn]; int dfn[maxn]; int cnt; vector<int>G[maxn << 1]; int fa[maxn]; bool incir[maxn]; void dfs1(int u, int _fa) { dfn[u] = ++cnt; for (int i = 0; i < gg[u].size();i++) { int v = gg[u][i]; if (v == _fa)continue; if (!dfn[v]) { fa[v] = u; dfs1(v, u); } else if (dfn[v] < dfn[u]) { ++nn; G[v].push_back(nn); incir[v] = true; fa[nn] = v; int tmp = u; while (tmp^v) { G[nn].push_back(tmp); incir[tmp] = true; tmp = fa[tmp]; } } } if (!incir[u])G[fa[u]].push_back(u); } int f[maxn<<1][2], dp[maxn<<1][2]; int st[maxn]; void solve(int u) { int top = 0; for (int i = 0; i < G[u].size();i++) { int v = G[u][i]; st[++top] = v; } dp[1][0] = f[st[1]][0]; dp[1][1] = -INF; for (int i = 2; i <= top; i++) { dp[i][1] = dp[i - 1][0] + f[st[i]][1]; dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + f[st[i]][0]; } f[u][0] = dp[top][0]; dp[top + 1][0] = dp[top + 1][1] = 0; for (int i = top; i >= 1; i--) { dp[i][1] = dp[i + 1][0] + f[st[i]][1]; dp[i][0] = max(dp[i + 1][0], dp[i + 1][1]) + f[st[i]][0]; } f[u][1] = max(dp[1][0], dp[1][1]); } void dfs2(int u) { f[u][0] = 0; f[u][1] = 1; for (int i = 0; i < G[u].size();i++) { int v = G[u][i]; dfs2(v); if (u <= n) { f[u][0] += max(f[v][0], f[v][1]); f[u][1] += f[v][0]; } } if (u > n) { solve(u); } } int main() { scanf("%d%d", &n, &m); nn = n; for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); gg[u].push_back(v); gg[v].push_back(u); } dfs1(1, 0); dfs2(1); cout << max(f[1][0], f[1][1]) << endl; return 0; }
|