<题目链接>
题目大意:
给你n个点和m条边,每条边代表两点具有匹配关系,问你有多少对匹配是冗余的。
解题分析:
所谓不冗余,自然就是这对匹配关系处于最大匹配中,即该匹配关系有意义。那怎样判断该匹配是否在最大匹配中呢?我们可以枚举每一对匹配,然后对其进行取消其匹配关系,对其余的匹配跑一遍最大匹配,如果是原始最大匹配-1,说明这对匹配关系在最大匹配关系中。需要注意的是,删除匹配关系的时候,不经要将该边的匹配关系删除,还需将所有点与这两点之间的匹配关系删除(即相当于删除这两点)。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 310
#define CLR(a,b) memset(a,b,sizeof(a))
deque<int> Q;
//g[i][j]存放关系图:i,j是否有边,match[i]存放i所匹配的点
bool g[MAXN][MAXN],inque[MAXN],inblossom[MAXN];
int match[MAXN],pre[MAXN],base[MAXN]; //找公共祖先
int findancestor(int u,int v)
{
bool inpath[MAXN]={false};
while()
{
u=base[u];
inpath[u]=true;
if(match[u]==-)break;
u=pre[match[u]];
}
while()
{
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]]=;
inblossom[base[v]]=;
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);
CLR(inblossom,);
reset(u,anc);reset(v,anc);
if(base[u]!=anc)pre[u]=v;
if(base[v]!=anc)pre[v]=u;
for(int i=;i<=n;i++)
if(inblossom[base[i]])
{
base[i]=anc;
if(!inque[i])
{
Q.push_back(i);
inque[i]=;
}
}
} bool dfs(int S,int n)
{
for(int i=;i<=n;i++)pre[i]=-,inque[i]=,base[i]=i;
Q.clear();Q.push_back(S);inque[S]=;
while(!Q.empty())
{
int u=Q.front();Q.pop_front();
for(int v=;v<=n;v++)
{
if(g[u][v]&&base[v]!=base[u]&&match[u]!=v)
{
if(v==S||(match[v]!=-&&pre[match[v]]!=-))contract(u,v,n);
else if(pre[v]==-)
{
pre[v]=u;
if(match[v]!=-)Q.push_back(match[v]),inque[match[v]]=;
else
{
u=v;
while(u!=-)
{
v=pre[u];
int w=match[v];
match[u]=v;
match[v]=u;
u=w;
}
return true;
}
}
}
}
}
return false;
} int solve(int n)
{
CLR(match,-);
int ans=;
for(int i=;i<=n;i++)
if(match[i]==-&&dfs(i,n))
ans++;
return ans;
}
/*-- 以上为带花树求一般图最大匹配的模板 --*/
bool vis[];
int a[],b[];
int main() {
int n , m;
while(scanf("%d%d",&n,&m) != EOF) {
CLR(g,false);CLR(vis,false);
for(int i = ; i <= m; i++) {
scanf("%d%d",&a[i],&b[i]);
g[a[i]][b[i]] = g[b[i]][a[i]] = true;
}
int ans = solve(n);
vector<int> vec;
for(int i = ; i <= m; i++) { //枚举不进行匹配边
int x = a[i] , y = b[i];
CLR(g,false); //清空匹配关系,接下来进行重置
for(int j = ; j <= m; j++) if(i!=j){
int tmp1 = a[j] , tmp2 = b[j];
if(tmp1==x||tmp1==y||tmp2==x||tmp2==y)continue; //为什么是将所有包含这两点之间匹配关系的全部(即删除点)清除 ???
g[tmp1][tmp2] = g[tmp2][tmp1] = true;
}
int tmp = solve(n);
if(tmp != ans - ) { //如果删除这条边后,最大匹配数不是原始值-1,说明这条边不在最大匹配中
vec.push_back(i);
}
}
printf("%d\n",vec.size());
if(vec.size()>) {
printf("%d",vec[]);
for(int i = ; i < vec.size(); i++) {
printf(" %d",vec[i]);
}
}
puts("");
}
return ;
}
2018-11-19