hdu 1689 Alien’s Necklace （bfs層次圖剪枝）

Alien’s Necklace

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1526 Accepted Submission(s): 415


Problem Description JYY is taking a trip to Mars. To get accepted by the Martians, he decided to make a magic necklace for their king. (Otherwise, JYY will be eaten) Now, he has collected many magic balls, and he is going to string them up.
Unfortunately, only particular pairs of balls can be adjacent in the necklace, otherwise they will explode. Notice that the first and the last ball in the necklace are also adjacent. Besides, the Martians think even numbers are unlucky, so the number of balls in the necklace must be odd. (Of course each ball can be used only once)
A necklace contains at least 3 balls. Because the balls are really precious, JYY wants the necklace has as few balls as possible. (Then he can give rest balls to his GF)
So JYY wonders the number of balls he has to use to make this necklace.

Input The input consists of several test cases. There is a single number above all, the number of cases. There are no more than 20 cases.
For each input, the first line contains 2 numbers N and M, N is the number of balls JYY collected, and M is the pairs of compatible balls. Balls are numbered from 1 to N. Followed M lines, each contains 2 numbers A and B, means that ball A and ball B are compatible. For each case, 0 < N <= 1,000, 0 < M <= 20,000.

Output If the gift can't be done, just print "Poor JYY." in a line, otherwise, print the minimal number of balls in the necklace. Use the format in the example.

Sample Input

2
5 6
1 2
2 4
1 3
3 5
4 3
4 5
2 1
1 2

Sample Output

Case 1: JYY has to use 3 balls.
Case 2: Poor JYY.

題意：讓找到一個環使得組成環的點數為奇數且點數至少為3,。

因為一個點可以多個途徑到達，但從一點出發第一次到達的肯定是最短路徑，又題目要求的奇偶性，每次到達一個點步數的奇偶性進行標記。

#include
#include
#include
#include
#include
using namespace std;
#define N 1005
#define ll __int64
const int inf=0x7fffffff;
vectorg[N];
int vis[N][2];
struct node
{
    int u,t;
    friend bool operator<(node a,node b)
    {
        return a.t>b.t;
    }
};
int bfs(int s)
{
    int i,u,v;
    priority_queueq;
    node cur,next;
    cur.u=s;
    cur.t=1;
    memset(vis,0,sizeof(vis));
    vis[s][1]=1;       //奇數點，用一個珠子
    q.push(cur);
    while(!q.empty())
    {
        cur=q.top();
        q.pop();
        u=cur.u;
        for(i=0;i3)   //結點處到達兩次，故應該減一
                return next.t-1;
            if(!vis[v][next.t%2])
            {
                vis[v][next.t%2]=1;
                q.push(next);
            }
        }
    }
    return inf;
}
int main()
{
    int i,n,m,u,v,tt,cnt=0;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            g[i].clear();
        while(m--)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int ans=inf;
        for(i=1;i<=n;i++)
            ans=min(ans,bfs(i));
        if(ans==inf)
            printf("Case %d: Poor JYY.\n",++cnt);
        else
            printf("Case %d: JYY has to use %d balls.\n",++cnt,ans);
    }
    return 0;
}

下面這種方法是用一個數組記錄到達該點的步數，當再次訪問該點時，說明出現環，直接判斷奇偶性就可以了。

又要求所用珠子數目大於三，所以要用一個pre變量記錄上一個節點的標號，判斷是否是兩點直接成環。

#include
#include
#include
#include
#include
using namespace std;
#define N 1005
#define ll __int64
const int inf=0x7fffffff;
vectorg[N];
int vis[N][2];
int ans;
struct node
{
    int u,t,pre;
    friend bool operator<(node a,node b)
    {
        return a.t>b.t;
    }
};
int bfs(int s)
{
    int i,u,v,t;
    priority_queueq;
    node cur,next;
    cur.u=s;
    cur.t=1;
    cur.pre=-1;
    memset(vis,0,sizeof(vis));
    vis[s][1]=1;
    q.push(cur);
    while(!q.empty())
    {
        cur=q.top();
        q.pop();
        u=cur.u;
        for(i=0;i