http://acm.hdu.edu.cn/showproblem.php?pid=3118二分图的性质：一个图十二分图，当且仅当图中不存在奇数环。
把点分成两个集合，把每个集合中相连的边删除即可。枚举所有集合，找出删除边最小的那个。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 20
#define MAX 0xfffffff
int mp[LEN][LEN];
int N, M;
int rs;
int tt;
int gd[LEN];
void DFS(int n)
{
if(n >= N)
{
int i, j;
tt = 0;
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++)
{
if(gd[i] == gd[j])
tt += mp[i][j];
}
if(tt < rs)
rs = tt;
}
else
{
gd[n] = 1;
DFS(n + 1);
gd[n] = 0;
DFS(n + 1);
}
}
int main()
{
int i, j;
int T;
int x, y;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &N, &M);
memset(mp, 0, sizeof(mp));
for(i = 0; i < M; i++)
{
scanf("%d%d", &x, &y);
mp[x][y]++;
mp[y][x]++;
}
memset(gd, 0, sizeof(gd));
rs = MAX;
DFS(0);
printf("%d\n", rs);
}
//system("pause");
return 0;
}
posted on 2012-09-04 22:39
小鼠标 阅读(215)
评论(0) 编辑 收藏 引用 所属分类:
图论 、
网选训练