Regionals 2012, Europe - Southwestern A.Beehives

此题不难，但是练习赛5小时内没有A掉.......最后还是因为没读清题意，多输出了一行空行

简化题意就是求无向图中的最小环问题。刚开始dfs找，tle了，才发现枚举每个点，再进行整幅图的dfs找最优解必然跪。

写bfs就好多了，枚举每个点，当广搜时碰到已经访问过的点并且不是它的前驱结点，此时就成环了。但不能退出广搜，必须继续搜索与之比较大小。

因为最先找到的环不一定是最小的环，同一层次上的点还是有先后搜索顺序的。

#include <iostream>  
#include <cstdio>  
#include <vector>  
#include <cstring>  
#include <queue>  
# define INF 0x7FFFFFFF  
using namespace std; 
int n,m; 
int minn; 
struct node { 
    int u,f; 
}; 
int sum[505]; 
int tmp,ok; 
vector<int> v[505]; 
 
void init() { 
    for(int i=0; i<=n; i++) { 
        v[i].clear(); 
    } 
    memset(sum,-1,sizeof(sum)); 
} 
 
void bfs(int u0) { 
    queue<node> q; 
    node t; 
    t.f = -1; 
    t.u = u0; 
    sum[u0] = 0; 
    q.push(t); 
    while(! q.empty()) { 
        t = q.front(); 
        node tt; 
        q.pop(); 
        int size = v[t.u].size(); 
        for(int i=0; i<size; i++) { 
            tt.f = t.u; 
            tt.u = v[t.u][i]; 
            if(tt.u == t.f) 
                continue; 
            if(sum[tt.u] == -1) { 
                q.push(tt); 
                sum[tt.u] = sum[t.u] + 1; 
            } else if(sum[tt.u] + sum[t.u] > 1 ) { 
                int tmp = sum[tt.u] + sum[t.u] + 1; 
                if(minn > tmp) minn = tmp; 
            } 
        } 
    } 
} 
 
int main() { 
    int t,i,j,a,b; 
    cin >> t; 
    int casee = 1; 
    while(t --) { 
        scanf("%d%d",&n,&m); 
        init(); 
        for(i=0; i<m; i++) { 
            scanf("%d%d",&a,&b); 
            v[a].push_back(b); 
            v[b].push_back(a); 
        } 
        printf("Case %d: ",casee++); 
        minn = INF; 
        for(i=0; i<n; i++) { 
            memset(sum,-1,sizeof(sum)); 
            //ok = 0;  
            bfs(i); 
        } 
        if(minn == INF) cout << "impossible" << endl; 
        else cout << minn << endl; 
    } 
    return 0; 
}

补充：软件开发 , C++ ,