標題來源：Light OJ 1406 Assassin`s Creed

意甲冠軍：向圖 派出最少的人經過全部的城市 而且每一個人不能走別人走過的地方

思路：最少的的人能夠走全然圖 明顯是最小路徑覆蓋問題 這里可能有環 所以要縮點 可是看例子又發現 一個強連通分量可能要拆分 n最大才15 所以就狀態壓縮?

將全圖分成一個個子狀態 每一個子狀態縮點 求最小路徑覆蓋 這樣就攻克了一個強連通分量拆分的問題 最后狀態壓縮DP求解最優值

#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <stack> using namespace std; const int maxn = 16; vector <int> G[maxn], G2[maxn]; int dp[1<<maxn]; int pre[maxn], low[maxn], sccno[maxn]; int clock, scc_cnt; int n, m; stack <int> S; int a[maxn][maxn]; int b[maxn][maxn];void dfs(int u, int x) {pre[u] = low[u] = ++clock;S.push(u);for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(!(x&(1<<v)))continue;if(!pre[v]){dfs(v, x);low[u] = min(low[u], low[v]); }else if(!sccno[v]){low[u] = min(low[u], pre[v]);}}if(pre[u] == low[u]){scc_cnt++;while(1){int x = S.top(); S.pop();sccno[x] = scc_cnt;if(x == u)break;}} } int find_scc(int x) {memset(sccno, 0, sizeof(sccno));memset(pre, 0, sizeof(pre));scc_cnt = 0, clock = 0;for(int i = 0; i < n; i++){if(x&(1<<i) && !pre[i])dfs(i, x);}return scc_cnt; }int y[maxn]; bool vis[maxn];bool xyl(int u) {for(int i = 0; i < G2[u].size(); i++){int v = G2[u][i];if(vis[v])continue;vis[v] = true;if(y[v] == -1 || xyl(y[v])){y[v] = u;return true;}}return false; } int match() {int ans = 0;memset(y, -1, sizeof(y));for(int i = 1; i <= scc_cnt; i++){memset(vis, false, sizeof(vis));if(xyl(i))ans++;}return scc_cnt-ans; } int main() {int cas = 1;int T;scanf("%d", &T);while(T--){scanf("%d %d", &n, &m);for(int i = 0; i < n; i++)G[i].clear();memset(a, 0, sizeof(a));while(m--){int u, v;scanf("%d %d", &u, &v);u--;v--;G[u].push_back(v);a[u][v] = 1;}dp[0] = 0;//puts("sdf");for(int i = 1; i < (1<<n); i++){//memset(b, 0, sizeof(b));find_scc(i);for(int j = 0; j <= n; j++)G2[j].clear();for(int j = 0; j < n; j++)for(int k = 0; k < n; k++)if(a[j][k] && sccno[j] && sccno[k] && sccno[j] != sccno[k])G2[sccno[j]].push_back(sccno[k]);dp[i] = match();}//puts("sdf");for(int s = 1; s < (1<<n); s++){for(int i = s; i; i = s&(i-1)){dp[s] = min(dp[s], dp[s^i] + dp[i]);}}printf("Case %d: %d\n", cas++, dp[(1<<n)-1]);}return 0; }

轉載于:https://www.cnblogs.com/blfshiye/p/4594571.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Light OJ 1406 Assassin`s Creed 减少国家DP+支撑点甚至通缩+最小路径覆盖的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。