HDU 4687 一般图带花树匹配+枚举

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4687
题目大意：有n个女孩。有m个候选组合。每个组合只有2个人。一个女孩可能属于零个或多个候选组合，但一个人只能注册为一个正式组合的成员。主办方希望今年能有尽可能多的正式组合参加。在这些限制下，某些候选组合实际上是多余的，因为只要必须最大化形式组合的数量，就不可能将其注册为形式组合。（就是就是这个候选组合不可能存在任意一个最大化形式组合方案中）
思路：我们先跑个最大匹配ans。然后枚举每条边u-v。如果假设这条边已经匹配。那么所有g[u][i]=g[i][u]=g[v][i]=g[i][v]=0。然后再跑个最大匹配ans1。如果ans1==ans-1。说明这条边是可以存在最大匹配的方案中。如果ans1<ans-1。说明条边是多余的。再把边还原。继续枚举下一条边。

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
#define MAXN 250
#define SET(a,b) memset(a,b,sizeof(a))
deque<int> Q;
//g[i][j]存放关系图：i,j是否有边,match[i]存放i所匹配的点
//建图开始初始化g
//最终匹配方案为match
//复杂度O(n^3)
//点是从1到n的
bool g[MAXN][MAXN],inque[MAXN],inblossom[MAXN],inpath[MAXN];
int match[MAXN],pre[MAXN],base[MAXN];

//找公共祖先
int findancestor(int u,int v){
    memset(inpath,false,sizeof(inpath));
    while(1){
        u=base[u];
        inpath[u]=true;
        if(match[u]==-1)break;
        u=pre[match[u]];
    }
    while(1){
        v=base[v];
        if(inpath[v])return v;
        v=pre[match[v]];
    }
}

//压缩花
void reset(int u,int anc){
    while(u!=anc){
        int v=match[u];
        inblossom[base[u]]=1;
        inblossom[base[v]]=1;
        v=pre[v];
        if(base[v]!=anc)pre[v]=match[u];
        u=v;
    }
}

void contract(int u,int v,int n){
    int anc=findancestor(u,v);
    SET(inblossom,0);
    reset(u,anc);reset(v,anc);
    if(base[u]!=anc)pre[u]=v;
    if(base[v]!=anc)pre[v]=u;
    for(int i=1;i<=n;i++)
        if(inblossom[base[i]]){
            base[i]=anc;
            if(!inque[i]){
                Q.push_back(i);
                inque[i]=1;
            }
        }
}

bool bfs(int S,int n){
    for(int i=0;i<=n;i++)pre[i]=-1,inque[i]=0,base[i]=i;
    Q.clear();Q.push_back(S);inque[S]=1;
    while(!Q.empty()){
        int u=Q.front();Q.pop_front();
        for(int v=1;v<=n;v++){
            if(g[u][v]&&base[v]!=base[u]&&match[u]!=v){
                if(v==S||(match[v]!=-1&&pre[match[v]]!=-1))contract(u,v,n);
                else if(pre[v]==-1){
                    pre[v]=u;
                    if(match[v]!=-1)Q.push_back(match[v]),inque[match[v]]=1;
                    else{
                        u=v;
                        while(u!=-1){
                            v=pre[u];
                            int w=match[v];
                            match[u]=v;match[v]=u;
                            u=w;
                        }
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int solve(int n){
    SET(match,-1);
    int ans=0;
    for(int i=1;i<=n;i++)
        if(match[i]==-1&&bfs(i,n))
            ans++;
    return ans;
}

int x[MAXN], y[MAXN], id[MAXN], tot=0;;
int main(){
    int n, m;
    while(~scanf("%d%d",&n, &m)){
        memset(g,false,sizeof(g));
        int a, b; tot=0;
        for(int i=1; i<=m; i++){
            scanf("%d%d",&a,&b);
            g[a][b]=g[b][a]=1;
            x[i]=a, y[i]=b;

        }
        int ans=solve(n);
        for(int i=1; i<=m; i++){
            int px[MAXN]={0}, py[MAXN]={0};
            a=x[i], b=y[i];
            for(int i=1; i<=n; i++){
                px[i]=g[a][i]; py[i]=g[b][i];
            }
            for(int i=1; i<=n; i++){
                g[a][i]=g[i][a]=g[b][i]=g[i][b]=0;
            }
            int Ts=solve(n);
            if(Ts<ans-1){
                id[++tot]=i;
            }
            for(int i=1; i<=n; i++){
                g[a][i]=g[i][a]=px[i];
                g[b][i]=g[i][b]=py[i];
            }
        }
        printf("%d\n", tot);
        for(int i=1; i<=tot; i++){
            printf("%d", id[i]);
            if(i<tot) printf(" ");
        }
        printf("\n");
    }
    return 0;
}