wordpress loper,国内seo工具,西平县建设局网站,做音乐网站没有版权标题来源#xff1a;Light OJ 1406 Assassins Creed 意甲冠军#xff1a;向图 派出最少的人经过全部的城市 而且每一个人不能走别人走过的地方 思路#xff1a;最少的的人能够走全然图 明显是最小路径覆盖问题 这里可能有环 所以要缩点 可是看例子又发现 一个强连通分量可能… 标题来源Light OJ 1406 Assassins 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[1maxn];
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(1v)))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(1i) !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 (1n); 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 (1n); 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[(1n)-1]);}return 0;
}转载于:https://www.cnblogs.com/blfshiye/p/4594571.html
