最大獨立集
?1.藍橋舞會
link:1.藍橋舞會 - 藍橋云課
分析：
code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAXN = 1e5 + 7;
ll hpy[MAXN], fa[MAXN], dp[MAXN][2];
vector<ll> sons[MAXN];void dfs(ll u, ll fa)
{for(ll son : sons[u]){dfs(son, u);dp[u][0] += max(dp[son][1], dp[son][0]);dp[u][1] += dp[son][0];}
}int main()
{ll n; cin>>n;for(int i = 1; i <= n; i++) cin>>hpy[i];// init dpfor(int i = 1; i <= n; i++) dp[i][1] = hpy[i];for(int i = 1; i <= n - 1; i++){ll u, v; cin>>u>>v;sons[v].push_back(u);fa[u] = v;}// find rootll root = 1;while(fa[root] != 0) root = fa[root];dfs(root, 0);ll ans = max(dp[root][0], dp[root][1]);cout<<ans<<endl;return 0;
}最小點覆蓋
例題：戰略游戲
link:P2016 戰略游戲 - 洛谷
分析：
code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll MAXN = 1507;
ll n, dp[MAXN][MAXN];
vector<ll> sons[MAXN];void dfs(ll root, ll fa)
{for (ll son : sons[root]){if (son == fa) continue;dfs(son, root);dp[root][0] += dp[son][1];dp[root][1] += min(dp[son][0], dp[son][1]);}
}int main()
{// inputcin >> n;for (int i = 0; i < n; i++){ll idx, k; cin >> idx >> k;for (int j = 1; j <= k; j++){ll s; cin >> s;sons[idx].push_back(s);sons[s].push_back(idx);}dp[idx][1] = 1;// init dp}// dfsdfs(0, -1);cout << min(dp[0][0], dp[0][1]) << endl;return 0;
}最小支配集
例題：皇宮守衛
題目：U224284 [提高]皇宮看守 - 洛谷
分析：
code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll MAXN = 1507;
ll n, kk[MAXN], dp[MAXN][3], ind[MAXN];
vector<ll> g[MAXN];void dfs(ll root, ll fa)
{ll _min = 1e18;// dfsfor (ll son : g[root]){//if (son == fa) continue;dfs(son, root);dp[root][0] += min({ dp[son][0], dp[son][1], dp[son][2] });dp[root][1] += min(dp[son][0], dp[son][1]);dp[root][2] += dp[son][1];_min = min(_min, dp[son][0] - min(dp[son][0], dp[son][1]));}dp[root][0] += kk[root];dp[root][1] += _min;// 確保至少一個son是0狀態（根節點被選中）// 當root為葉子節點時， min為極大值，代表dp[root][1]狀態不可取;(葉子節點不可能滿足1狀態條件，在root子樹中不被選中同時又被支配
}int main()
{// inputcin >> n;for (int i = 1; i <= n; i++){ll idx, k, m; cin >> idx >> k >> m; kk[idx] = k;for (int j = 1; j <= m; j++){ll r; cin >> r;g[idx].push_back(r);ind[r]++;//g[r].push_back(idx);}}ll root;for (int i = 1; i <= n; i++){if (ind[i] == 0){root = i;break;}}dfs(root, 0);cout << min(dp[root][0], dp[root][1]) << endl;return 0;
}
