标题来源：

problem=1406">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;

}