本文主要是介绍ural 1500 Pass Licenses --- 状态压缩dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这方法真好啊。。
有n个点，m条路，k个执照，每条路都属于一些执照（拥有指定执照才能走）
求从0走到1 最少需要哪些执照
枚举 1到1<<k 二进制的每一位代表是否拥有该执照
对每一种组合dfs 取二进制中1最少的解咯
代码很简洁 但熟练运用二进制总是需要多多练习的事。。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;//mp[i][j]中为1的位表示，拥有该位的执照就可以走i到j这条路
int mp[35][35],vis[35],k,n,m,tmp,ans1[35],ans,tmp1[35];void dfs(int x,int now)
{vis[x]=1;if(x==1) return;for(int i=0;i<n;i++){if((now&mp[x][i])&&!vis[i])dfs(i,now);}
}int main()
{int i,v1,v2,c,now,cnt,j;while(~scanf("%d%d%d",&k,&n,&m)){memset(mp,0,sizeof mp);for(i=0;i<m;i++){scanf("%d%d%d",&v1,&v2,&c);mp[v1][v2]=((1<<c)|mp[v1][v2]);mp[v2][v1]=mp[v1][v2];}ans=inf;for(i=0;i<(1<<k);i++)//k种执照的每种组合尝试一遍{tmp=i;cnt=0;while(tmp)//必要的剪枝{if(tmp&1)cnt++;tmp>>=1;}if(cnt>=ans) continue;now=i;memset(vis,0,sizeof vis);dfs(0,now);// printf("vis1:%d i:%d\n",vis[1],i);if(vis[1])//能够走到1 则比较执照数量{ans=0;cnt=0;while(now){// printf("tmp:%d cnt:%d\n",tmp,cnt);if(now&1){ans1[ans]=cnt;ans++;}now>>=1;cnt++;}}}printf("%d\n",ans);for(i=0;i<ans-1;i++)printf("%d ",ans1[i]);printf("%d\n",ans1[i]);}return 0;
}
这篇关于ural 1500 Pass Licenses --- 状态压缩dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
