是个PDF，不好复制进来。
大意：有个人要追个妹子，想加妹子QQ，但是不知道谁规定的，玩QQ的人要加好友必须先要有至少k个共同好友。共有N个人玩QQ，编号为1到N，1是男主，N是妹子。有M个初始好友关系，求男主最少要加多少个人才能有资格加妹子，或者永远加不到妹子。
题解：
最少加多少个人加到妹子，可以想到广搜，状态是男主的加好友情况。但广搜却不能一个人只进队一次，因为从不同的路径加到这个人，结果是不同的，让我们来看看这个情况：
N=8，M=11，K=2，男主需要加到6，再加到7，才能加到女主；但如果宽搜时每次加第i个新好友的情况只进队一次，则男主会同时加到6和7，然后从加6的情况或者加7的情况都加不到女主，又不能从6跳到7或者从7跳到6，因为他们已经进过队了，这样就逗乐。
但是广搜不剪枝会超时，各种各样的路线搞出来的情况还是很多的。所以我们要根据状态来，状态是男主的加好友情况（和哪些人是好友，因为只有20个人玩QQ，可以用一个int的20个二进制位来存），dis[x]记录状态x的走过的距离，如果再次走到状态x时，距离不小于上次的距离，则不用再进这个状态了。
我用的20个bool来存的状态，结果比全用位的慢0.5s，大概我转成int来操作dis[]的时候耗时太多。
代码：
1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<map> 8 #include<set> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define ll __int64 13 #define usint unsigned int 14 #define mz(array) memset(array, 0, sizeof(array)) 15 #define minf(array) memset(array, 0x3f, sizeof(array)) 16 #define REP(i,n) for(int i=0;i<(n);i++) 17 #define FOR(i,x,n) for(int i=(x);i<=(n);i++) 18 #define RD(x) scanf("%d",&x) 19 #define RD2(x,y) scanf("%d%d",&x,&y) 20 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 21 #define WN(x) printf("%d\n",x); 22 #define RE freopen("D.in","r",stdin) 23 #define WE freopen("1.out","w",stdout) 24 25 const int maxn=20; 26 27 struct arr{ 28 bool a[maxn+1]; 29 int dis; 30 }a[maxn]; 31 32 int n,m,k; 33 int dis[1<<maxn]; 34 35 int atox(arr b) 36 { 37 int re=0; 38 for(int i=1;i<=n;i++) 39 re=(re<<1)|b.a[i]; 40 return re; 41 } 42 43 int count_same(int x,int y) 44 { 45 int cnt=0; 46 for(int i=1;i<=n;i++) 47 if(a[x].a[i] && a[y].a[i])cnt++; 48 return cnt; 49 } 50 51 int gank() 52 { 53 int i; 54 if(a[1].a[n])return 0; 55 queue<arr>q; 56 a[1].dis=0; 57 q.push(a[1]); 58 while(!q.empty()) 59 { 60 a[1]=q.front(); 61 q.pop(); 62 for(i=2;i<=n;i++) 63 { 64 if(!a[1].a[i] && count_same(1,i)>=k) 65 { 66 arr next=a[1]; 67 next.a[i]=1; 68 next.dis++; 69 if(dis[atox(next)]<=next.dis)continue; 70 if(i==n) return a[1].dis; 71 q.push(next); 72 } 73 } 74 } 75 return -1; 76 } 77 78 int main() 79 { 80 int cas=1,i,T; 81 scanf("%d",&T); 82 while(T--) 83 { 84 RD3(n,m,k); 85 for(i=1;i<=n;i++) 86 memset(a[i].a,0,sizeof(a[i].a)); 87 for(i=1;i<=m;i++) 88 { 89 int u,v; 90 RD2(u,v); 91 a[u].a[v]=1; 92 a[v].a[u]=1; 93 } 94 for(i=1;i<=n;i++) 95 { 96 a[i].a[i]=1; 97 } 98 memset(dis,0x3f,sizeof(dis)); 99 dis[atox(a[1])]=0; 100 printf("Case #%d: %d\n",cas++,gank()); 101 } 102 return 0; 103 }
UVa12726 one Friend at a Time （位 广搜）,布布扣,bubuko.com
UVa12726 one Friend at a Time （位 广搜）
原文：http://www.cnblogs.com/yuiffy/p/3889587.html
