fzu_2181 快来买肉松饼

题目:

  转眼又到了一年一度的圣战(光棍)节了,单身狗大表哥决定和一群一样孤独的盆友一起出来过节,一起玩游戏,输的人给赢的人买肉松饼,这样大家都不会感到孤单。
  为了防止平局出现,大表哥给大家准备了一个奇数(大于一的奇数)个人可以围成一圈一起玩的游戏(每个人必须与两个人相邻)。大表哥希望大家都能参加到游戏里去,但无奈有些盆友之间有误会,有误会的盆友不能坐在相邻的位置一起愉快的玩耍。每个人可以同时参与多个游戏,但当所有能参与游戏的人数小于K时,大表哥将取消这次聚会。

思路:

  首先有一个结论:如果一个边双联通分量中存在一个奇环,那么这个分量中的每一个点都一定至少在某个奇环上。
  证明伪证:设现在存在一个每个点都在奇环上的边双联通分量(比如 )。现在要加入一个新点,因为要保证不出现桥,所以至少要连两条边,因为 是偶数,所以这个点一定会出现一个奇环上。
  那么只要求出边双后做一次二分图染色即可。复杂度

代码:

#include <cstdio>
#include <cstring>
#define rep(i, a, b) for(int i(a), i ##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i ##_END_(b); i >= i##_END_; i--)
#define mset(a, b) memset(a, b, sizeof a)
using namespace std;
const int N = 1005;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k = G.HEAD[o]; k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {tot = 0; mset(HEAD, 0);}
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
typedef Link<N, N * N, int> Graph;
Graph G, M;
bool edge[N][N];

struct Edge {
    int u, v;
    bool operator!= (const Edge e) const {
        return u != e.u || v != e.v;
    }
};
Edge stk[N * N];

int vis[N];
bool col[N];
bool dfs(int o, int t, Graph &G) {
    vis[o] = t;
    erep(k, G, o) {
        int v = G[k];
        if(vis[v] == t) {
            if(col[o] == col[v]) return false;
            continue;
        }
        col[v] = col[o] ^ 1;
        if(!dfs(v, t, G)) return false;
    }
    return true;
}
bool check(int vec[], int tot, Graph &G) {
    static int cnt = 0;
    cnt++;
    rep(i, 1, tot) {
        int v = vec[i];
        if(vis[v] != cnt && !dfs(v, cnt, G))
            return false;
    }
    return true;
}

int dfn[N], low[N], top, cur, bcnt;
int mark[N], vec[N];
bool ans[N];
void tarjan(int o, int f) {
    dfn[o] = low[o] = ++cur;
    erep(k, G, o) {
        int v = G[k];
        if(v == f) continue;
        if(!dfn[v]) {
            stk[++top] = (Edge) {o, v};
            tarjan(v, o);
            tomin(low[o], low[v]);
            int tot = 0;
            if(low[v] >= dfn[o]) {
                bcnt++;
                do {
                    Edge e = stk[top];
                    if(mark[e.u] != bcnt) {
                        vec[++tot] = e.u;
                        mark[e.u] = bcnt;
                    }
                    if(mark[e.v] != bcnt) {
                        vec[++tot] = e.v;
                        mark[e.v] = bcnt;
                    }
                    M.add(e.u, e.v);
                    M.add(e.v, e.u);
                } while(stk[top--] != (Edge) {o, v});
                if(!check(vec, tot, M)) 
                    rep(i, 1, tot) ans[vec[i]] = 1;
                rep(i, 1, tot) M.HEAD[vec[i]] = 0;
                M.tot = 0;
            }
        } 
        else if(dfn[v] < dfn[o]) {
            tomin(low[o], dfn[v]);
            stk[++top] = (Edge) {o, v};
        }
    }
}

int main() {
    int cas, n, m, k;
    scanf("%d", &cas);
    while(cas--) {
        G.clear();
        scanf("%d%d%d", &n, &m, &k);
        mset(edge, 0);
        rep(i, 1, m) {
            int x, y;
            scanf("%d%d", &x, &y);
            edge[x][y] = edge[y][x] = true;
        }
        rep(i, 1, n) 
            rep(j, 1, n)
                if(!edge[i][j] && i != j)
                    G.add(i, j);
        mset(dfn, 0); mset(ans, 0);
        rep(i, 1, n) 
            if(!dfn[i]) 
                tarjan(i, 0);
        int tmp = 0;
        rep(i, 1, n) tmp += ans[i];
        puts(tmp < k ? "What a Pity." : "Let's Fire!");
    }
    return 0;
}