http://acm.hdu.edu.cn/showproblem.php?pid=3118二分圖的性質：一個圖十二分圖，當且僅當圖中不存在奇數(shù)環(huán)。
把點分成兩個集合，把每個集合中相連的邊刪除即可。枚舉所有集合，找出刪除邊最小的那個。
#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
小鼠標 閱讀(226)
評論(0) 編輯 收藏 引用 所屬分類:
圖論 、
網(wǎng)選訓練