题意：有一张有向图，一个刺客不能走别的刺客走过的点（能多次经过自己走过的点），问最少需要几名刺客，才能把每个点的目标干掉
思路：很容易想到，一个环，走一圈回到起点，相当于一个点，SCC缩点后，求最小路径覆盖，但我们发现第二个样例，它把一个连通集拆开了。那么我们状压DP每一个子图，每个子图用上面的方法，求一遍最小路径覆盖。最后每个大的状态，可以有两个小的状态的值相加，取最小值
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<stdlib.h> #include<math.h> #include<vector> #include<list> #include<map> #include<stack> #include<queue> #include<algorithm> #include<numeric> #include<functional> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int maxn = 30; int dp[1<<16]; struct edge { int to,next; bool cut; }ed[100]; int head[maxn], tot; int Low[maxn], DFN[maxn], Stack[maxn]; int Index, top; bool Instack[maxn]; int block,belong[maxn]; int bridge; vector<int> v[maxn]; int girl[maxn],vis[maxn]; void init() { memset(DFN, 0, sizeof(DFN)); memset(Instack, false, sizeof(Instack)); block = 0; Index = top = 0; bridge = 0; memset(girl,-1,sizeof girl); for(int i = 1; i <= 18; i++) v[i].clear(); } int fid(int x) // 为匹配x { for(int l = 0; l < v[x].size(); l++) { int j = v[x][l]; if(!vis[j]/* && line[x][j]*/) { vis[j] = 1; if(girl[j] == -1 || fid(girl[j]) ) { girl[j] = x; return 1; } } } return 0; } void addedge(int x,int y) { v[x].push_back(y); } void Tarjan(int s,int u,int pre) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];i != -1;i = ed[i].next) { v = ed[i].to; if((s&(1<<(v-1)))==0) continue; //if(v == pre)continue; //无向无重边 用，只要不往回走 //if(ed[i].id == pre) continue; //无向图重边判定，不走同一条边 if( !DFN[v] ) { Tarjan(s,v,u); //Tarjan(v,ed[i].id); //无向图重边判定 if( Low[u] > Low[v] )Low[u] = Low[v]; if(Low[v] > DFN[u]) { bridge++; ed[i].cut = true; ed[i^1].cut = true; } } else if( Instack[v] && Low[u] > DFN[v] ) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { block++; do { v = Stack[--top]; Instack[v] = false; belong[v] = block; } while( v!=u ); } } void add(int x,int y) { ed[tot].to = y; ed[tot].next = head[x]; ed[tot].cut = 0; //ed[tot].id = num; //无向图重边判定 head[x] = tot++; } void SCC(int s,int n) { for(int i=1; i<=n; i++) if(!DFN[i] && s&(1<<(i-1))) Tarjan(s,i,-1); } int main(void) { int T,n,m,kase = 1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); tot = 0; memset(head, -1, sizeof(head)); for(int i = 1; i <= m; i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); } int en = (1<<n) - 1; for(int s = 1; s <= en; s++) { init(); SCC(s,n); for(int i = 1; i <= n; i++) { if((s & 1<<(i-1))==0) continue; for(int j = head[i]; j != -1 ; j = ed[j].next) { int k = ed[j].to; if(s & 1<<(k-1)) { if(belong[i] != belong[k]) addedge(belong[i],belong[k]); } } } int num = 0; for(int i = 1; i <= block; i++) { memset(vis,0,sizeof vis); if(fid(i)) num++; } dp[s] = block - num; } for(int s = 2; s <= en; s++) { for(int i = s; i ; i = s & (i-1)) dp[s] = min(dp[s],dp[i] + dp[s^i]); } printf("Case %d: %d\n",kase++,dp[en]); } return 0; }
