http://acm.hdu.edu.cn/showproblem.php?pid=3118
题意：删除最少的边使图没有奇环
二分图的定义：如果顶点能分为两个互不相交的子集，则图为二分图
二分图的判定：如果二分图能黑白染色成功，则图为二分图
而黑白染色，其实就是判断环是奇环还是偶环
如果是奇环，一定会有黑黑或白白相撞
所以删除最小的边使图没有奇环，就是使图能够黑白染色
也就是删除最少的边，使图变成一个二分图
n只有15
完全可以枚举左边有哪些点，右边有哪些点
因为二分图的两个点集互不相交
所以两个点集内部的边数
就是使当前点的分布状态能形成二分图需要删去的边数
所有枚举的状态取最小
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int e[][];
int a[],b[];
int n;
int solve(int S)
{
a[]=b[]=;
for(int i=;i<n;i++)
if(S&(<<i)) a[++a[]]=i+;
else b[++b[]]=i+;
int r=;
for(int i=;i<=a[];i++)
for(int j=i+;j<=a[];j++)
{
if(i==j) continue;
r+=e[a[i]][a[j]];
}
for(int i=;i<=b[];i++)
for(int j=i+;j<=b[];j++)
{
if(i==j) continue;
r+=e[b[i]][b[j]];
}
return r;
}
int main()
{
int S,T,m,u,v,ans;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(e,false,sizeof(e));
ans=m+;
while(m--)
{
scanf("%d%d",&u,&v);
u++; v++;
e[u][v]++; e[v][u]++;
}
S=<<n;
for(int i=;i<S;i++) ans=min(ans,solve(i));
printf("%d\n",ans);
}
}