HDU 3118 Arbiter 二分图？

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=3118

题意

问最少删除几条边，使图不含奇圈

思路

据说二分图就是不含奇圈的，那就枚举左边和右边的点吧，把同侧的点之间的边删掉，找到最小的。

#include<cstdio> #include<cstring> #include<algorithm> const int maxn = 20; const int INF = 1<<30; int g[maxn][maxn]; using namespace std; int n,m; int Get(int u) { int ans=0; for(int i=0;i<n;i++) if(u&(1<<i)) for(int j=i+1;j<n;j++) if(u&(1<<j)) ans+=g[i][j]; return ans; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(g,0,sizeof(g)); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); g[u][v]++;g[v][u]++; // 有重边 } int ans=INF; for(int i=0;i<(1<<n);i++) { int temp=i^((1<<n)-1); ans=min(ans,Get(i)+Get(temp)); } printf("%d\n",ans); } }