LightOJ1406Assassin`sCreed状态压缩DP+强连通缩点+最小路径覆盖

题目来源：Light OJ 1406 Assassin`s Creed

题意：有向图 派出最少的人经过所有的城市 并且每个人不能走别人走过的地方

思路：最少的的人可以走完全图 明显是最小路径覆盖问题 这里可能有环 所以要缩点 但是看样例又发现 一个强连通分量可能要拆分 n最大才15 所以就状态压缩 

将全图分成一个个子状态 每个子状态缩点 求最小路径覆盖 这样就解决了一个强连通分量拆分的问题 最后状态压缩DP求解最优值

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 16;
vector  G[maxn], G2[maxn];
int dp[1<int pre[maxn], low[maxn], sccno[maxn];
int clock, scc_cnt;
int n, m;
stack  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 {
int v = G[u][i];
if(!(x&(1<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 {
if(x&(1<dfs(i, x);
}
return scc_cnt;
}

int y[maxn];
bool vis[maxn];

bool xyl(int u)
{
for(int i = 0; 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 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<{
//memset(b, 0, sizeof(b));
find_scc(i);
for(int j = 0; j <= n; j++)
G2[j].clear();
for(int j = 0; j for(int k = 0; 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<{
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<}
return 0;
}