【题目链接】
http://acm.hdu.edu.cn/showproblem.php?pid=1689
【题目大意】
给定N个珠子，从1到N编号，然后是M个配对关系(x,y)，表示珠子x和y可以相邻，要求用最少的珠子组成串，且所用珠子个数是大于或等于3的奇数，求这个最小的珠子个数的值。
【详细分析】
刚开始看到题，是自己刚刚挂的一个DIY：2008“Sunline Cup”邀请赛里的第一题，大概的想了下，觉得可以转换成最小环来做，刚好自己会最小环（可以参考我的最小环相关博文，很详细）。数据量是1000，觉得Floyd算法应该可以吧，就写了，结果是超时。赛后自己百度，看了很多讲解，下面给出整理之后的详细题解。
（待要到100ms以内的代码再行补之，见谅）
【AC代码】
/*2011-02-06 19:39:27 Accepted 1689 437MS 588K 1884 B C++ *///http://www.cnblogs.com/zhuangli/articles/1285516.html
#include<iostream>#include<stdio.h>#include<queue>using namespace std;struct Edge{ int next,v;}edge[40010];int idx;int n,m,dp[1005],p[1005]; bool vis[1005];struct Node{int v;};queue<Node>Q;queue<Node>save;void Addedge(int a,int b){ edge[idx].next=p[a]; edge[idx].v=b; p[a]=idx++;} void BFS(){ int i,res=INT_MAX; for(i=1;i<=n;i++){ while(!Q.empty()) Q.pop(); memset(vis,0,sizeof(vis)); Node st; st.v=i; dp[i]=0; Q.push(st); vis[i]=1; int len=0,j,v; while(!Q.empty()&& ++len<res){ while(!save.empty()) save.pop(); while(!Q.empty()){ //逐层扩展； Node t=Q.front(); Q.pop(); for(j=p[t.v];j!=-1;j=edge[j].next){ v=edge[j].v; if(vis[v]){ int now=dp[v]+len; if(now<res&&now&1) res=now; } else{ Node tt; tt.v=v; save.push(tt); vis[v]=1; dp[v]=len; } } } while(!save.empty()){ Q.push(save.front()); save.pop(); } } } if(res==INT_MAX) puts("Poor JYY."); else printf("JYY has to use %ld balls./n",res); }int main(){ int T,x,y,TT=0; scanf("%d",&T); while(T--) { memset(p,-1,sizeof(p)); scanf("%d%d",&n,&m); idx=0; while(m--){ scanf("%d%d",&x,&y); Addedge(x,y); swap(x,y); Addedge(x,y); } printf("Case %d: ",++TT); BFS(); }}
