题目链接
题意：
给定一张有向图，问最少能拆成几条路径要求包含所有点 且 不同路径之间没有重点，同一可以重复经过同一点(点数<=15,边数<=40)
思路：
定义
ok[x][y]：x集合是否存在一条以y点结尾的路径
dp[x] ：x集合的最少路径数
dp[x] = min( dp[i] + dp[j] ) i^j==x && i&j==0
因为有环，那么每次处理出一个可行的ok[x][y]时，dfs()找x集合其他可行的结束点
代码：
#include<bits/stdc++.h> using namespace std; bool G[15][15]; bool ok[1<<15][15]; int dp[1<<15]; bool check(int x,int t){ for(int i=0;i<15;i++)if(ok[x][i]&&G[i][t]) return true; return false; } void Dfs(int x,int t){ for(int i=0,j=1;j<=x;i++,j<<=1) if((x&j)&&G[t][i]&&!ok[x][i]){ ok[x][i] = true; Dfs(x,i); } } void work(int x){ dp[x] = 0; for(int i=0,j=1;j<=x;i++,j<<=1){ if((j&x) && !ok[x][i] ){ int t = j^x; if(!t||check(t,i)){ ok[x][i]=true; Dfs(x,i); } }if(ok[x][i])dp[x]=1; } } int main() { int T,Cas=0;scanf("%d",&T); while(T--){ memset(G,0,sizeof(G)); memset(ok,0,sizeof(ok)); ok[0][0]=true; int n,m;scanf("%d%d",&n,&m); while(m--){ int s,t;scanf("%d%d",&s,&t);--s;--t; G[s][t]=1; }int ed = (1<<n); for(int i=1;i<ed;++i)work(i); for(int i=1;i<ed;++i)if(!dp[i]){dp[i] = 100; for(int j=i;j;j=i&(j-1)) dp[i] = min(dp[i],dp[j]+dp[i^j]); }printf("Case %d: %d\n",++Cas,dp[ed-1]); }return 0; }
