一般图的最大匹配(带花树)

不只是二分图，一般图也能求最大匹配

ZOJ 3316 GAME

平面上有N个点，两个人轮流取平面上曼哈顿距离不大于L的点，谁没有点取谁就输，问后手能不能赢。

求图中每个连通分量的最大匹配，如果每个匹配都是完全匹配，后手一定赢，他每次都走先手的匹配点即可；如果某个匹配不是完全匹配，先手在这个连通分量上随便找一个点开始走，后手最后一定找不到可走的点。

#include <cstdio>
#include <cstring>

const int MAXN = 500;
int N, L;
bool Graph[MAXN][MAXN];
int Match[MAXN];
bool InQueue[MAXN],InPath[MAXN],InBlossom[MAXN];
int Head,Tail;
int Queue[MAXN];
int Start,Finish;
int NewBase;
int Father[MAXN],Base[MAXN];
int Count;
struct point {
    int x, y;
}p[MAXN];

inline int abs(int a) {
    return  a > 0 ? a : -a;
}

void CreateGraph() {
    memset(Graph,false,sizeof(Graph));
    for (int i = 1; i <= N; i++)
        scanf("%d%d", &p[i].x, &p[i].y);
    scanf("%d", &L);
    for (int i = 1; i <= N; i++)
        for (int j = i+1; j <= N; j++)
            if (abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y) <= L)
                Graph[i][j] = Graph[j][i] = true;
}

void Push(int u) {
    Queue[Tail] = u;
    Tail++;
    InQueue[u] = true;
}

int Pop() {
    int res = Queue[Head];
    Head++;
    return res;
}

int FindCommonAncestor(int u,int v) {
    memset(InPath,false,sizeof(InPath));
    while(true) {
        u = Base[u];
        InPath[u] = true;
        if(u == Start) break;
        u = Father[Match[u]];
    }

    while(true) {
        v = Base[v];
        if(InPath[v])break;
        v = Father[Match[v]];
    }
    return v;
}

void ResetTrace(int u) {
    int v;
    while(Base[u] != NewBase) {
        v = Match[u];
        InBlossom[Base[u]] = InBlossom[Base[v]] = true;
        u = Father[v];
        if(Base[u] != NewBase) Father[u] = v;
    }
}

void BloosomContract(int u,int v) {
    NewBase = FindCommonAncestor(u,v);
    memset(InBlossom,false,sizeof(InBlossom));
    ResetTrace(u);
    ResetTrace(v);
    if(Base[u] != NewBase) Father[u] = v;
    if(Base[v] != NewBase) Father[v] = u;
    for(int tu = 1; tu <= N; tu++)
        if(InBlossom[Base[tu]]) {
            Base[tu] = NewBase;
            if(!InQueue[tu]) Push(tu);
        }
}

void FindAugmentingPath() {
    memset(InQueue,false,sizeof(InQueue));
    memset(Father,0,sizeof(Father));
    for(int i = 1;i <= N;i++)
        Base[i] = i;
    Head = Tail = 1;
    Push(Start);
    Finish = 0;
    while(Head < Tail) {
        int u = Pop();
        for(int v = 1; v <= N; v++)
            if(Graph[u][v] && (Base[u] != Base[v]) && (Match[u] != v)) {
                if((v == Start) || ((Match[v] > 0) && Father[Match[v]] > 0))
                    BloosomContract(u,v);
                else if(Father[v] == 0) {
                    Father[v] = u;
                    if(Match[v] > 0)
                        Push(Match[v]);
                    else {
                        Finish = v;
                        return;
                    }
                }
            }
    }
}

void AugmentPath() {
    int u,v,w;
    u = Finish;
    while(u > 0) {
        v = Father[u];
        w = Match[v];
        Match[v] = u;
        Match[u] = v;
        u = w;
    }
}

void Edmonds() {
    memset(Match,0,sizeof(Match));
    for(int u = 1; u <= N; u++)
        if(Match[u] == 0) {
            Start = u;
            FindAugmentingPath();
            if(Finish > 0)AugmentPath();
        }
}

void PrintMatch() {
    Count = 0;
    for(int u = 1; u <= N; u++)
        if(Match[u] > 0)
            Count++;
    //    printf("%d\n",Count);
    //  for(int u = 1; u <= N; u++)
    ////    if(u < Match[u])
    //    printf("%d %d\n",u,Match[u]);
    if (Count == N) printf("YES\n");
    else printf("NO\n");
}

int main() {
    while (scanf("%d", &N) != EOF) {
        CreateGraph();
        Edmonds();
        PrintMatch();
    }
    return 0;
}

HDU 4687 Boke and Tsukkomi

给出N个点M条边的一个图，求哪几条边不在这个图的任意一个最大匹配中。

设没删任何一条边的时候的最大匹配数为K，枚举每一条边e[i]，假设这条边在最大匹配上所以删去和e[i].u，e[i].v相连的每一条边，若此时的匹配数为K-1，此边一定在某个最大匹配上并把它标记。枚举M次后没有被标记的边就是不在任何一个最大匹配上的边。

注意可能所有边都在最大匹配上，这时候要输出一个空行。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 500 + 5;
int N, M;
bool G[MAXN][MAXN];
int Match[MAXN];
bool InQueue[MAXN],InPath[MAXN],InBlossom[MAXN];
int Head,Tail;
int Queue[MAXN];
int Start,Finish;
int NewBase;
int Father[MAXN],Base[MAXN];
int Count;

struct point {
    int x, y;
}p[MAXN];

struct edge {
    int u, v;
}e[MAXN * MAXN];

void CreateG() {
    memset(G,false,sizeof(G));
    int u, v;
    for (int i = 0; i < M; i++) {
        scanf("%d%d", &u, &v);
        G[u][v] = G[v][u] = true;
        e[i+1].u = u; e[i+1].v = v;
    }
}

void Push(int u) {
    Queue[Tail] = u;
    Tail++;
    InQueue[u] = true;
}

int Pop() {
    int res = Queue[Head];
    Head++;
    return res;
}

int FindCommonAncestor(int u,int v) {
    memset(InPath,false,sizeof(InPath));
    while(true) {
        u = Base[u];
        InPath[u] = true;
        if(u == Start) break;
        u = Father[Match[u]];
    }

    while(true) {
        v = Base[v];
        if(InPath[v])break;
        v = Father[Match[v]];
    }
    return v;
}

void ResetTrace(int u) {
    int v;
    while(Base[u] != NewBase) {
        v = Match[u];
        InBlossom[Base[u]] = InBlossom[Base[v]] = true;
        u = Father[v];
        if(Base[u] != NewBase) Father[u] = v;
    }
}

void BloosomContract(int u,int v) {
    NewBase = FindCommonAncestor(u,v);
    memset(InBlossom,false,sizeof(InBlossom));
    ResetTrace(u);
    ResetTrace(v);
    if(Base[u] != NewBase) Father[u] = v;
    if(Base[v] != NewBase) Father[v] = u;
    for(int tu = 1; tu <= N; tu++)
        if(InBlossom[Base[tu]]) {
            Base[tu] = NewBase;
            if(!InQueue[tu]) Push(tu);
        }
}

void FindAugmentingPath() {
    memset(InQueue,false,sizeof(InQueue));
    memset(Father,0,sizeof(Father));
    for(int i = 1;i <= N;i++)
        Base[i] = i;
    Head = Tail = 1;
    Push(Start);
    Finish = 0;
    while(Head < Tail) {
        int u = Pop();
        for(int v = 1; v <= N; v++)
            if(G[u][v] && (Base[u] != Base[v]) && (Match[u] != v)) {
                if((v == Start) || ((Match[v] > 0) && Father[Match[v]] > 0))
                    BloosomContract(u,v);
                else if(Father[v] == 0) {
                    Father[v] = u;
                    if(Match[v] > 0)
                        Push(Match[v]);
                    else {
                        Finish = v;
                        return;
                    }
                }
            }
    }
}

void AugmentPath() {
    int u,v,w;
    u = Finish;
    while(u > 0) {
        v = Father[u];
        w = Match[v];
        Match[v] = u;
        Match[u] = v;
        u = w;
    }
}

void Edmonds() {
    memset(Match,0,sizeof(Match));
    for(int u = 1; u <= N; u++)
        if(Match[u] == 0) {
            Start = u;
            FindAugmentingPath();
            if(Finish > 0)AugmentPath();
        }
}

int PrintMatch() {
    Count = 0;
    for(int u = 1; u <= N; u++)
        if(Match[u] > 0)
            Count++;
    return Count;
    //  printf("%d\n",Count);
    //  for(int u = 1; u <= N; u++)
    //      if(u < Match[u])
    //          printf("%d %d\n",u,Match[u]);
}

vector<int>ans;

int vis[MAXN];

void Solve() {
    memset(vis, 0, sizeof(vis));
    ans.clear();
    int maxmatch = PrintMatch() / 2;
    for (int i = 1; i <= M; i++) {
        memset(G, 0, sizeof(G));
        int u = e[i].u, v = e[i].v;
        for (int j = 1; j <= M; j++) if (i != j){
            if (e[j].u == u || e[j].v == u || e[j].u == v ||
                    e[j].v == v) continue;
            G[e[j].u][e[j].v] = G[e[j].v][e[j].u] = 1;
        }
        Edmonds();
        int k = PrintMatch() / 2;
        if (k == maxmatch-1)
            vis[i] = 1;
    }
    for (int i = 1; i <= M; i++) if (!vis[i]) ans.push_back(i);
    int sz = ans.size();
    printf("%d\n", sz);
    if (sz > 0) {
        printf("%d", ans[0]);
        for (int i = 1; i < sz; i++) {
            printf(" %d", ans[i]);
        }
    }
    puts("");
}

int main() {
    //freopen("in.txt", "r", stdin);
    while (scanf("%d%d", &N, &M) != EOF) {
        CreateG();
        Edmonds();
        Solve();
    }
    return 0;
}