Color Graph

K.Color Graph

题意：

给一个无向图n个点m条边，给一些边涂红色。要求红色边不能有奇环.求能染红的最多的边。

解题：

题目中讲到了奇环， 这很容易往二分图上想。

定理：一个无向图是二分图，当且仅当图中不存在奇环

接下里就是找是二分图的最多的边。
我们一般是分两个集合进行操作，在这个题中由于n最大值为16，所以我们可以用二进制进行枚举对n个点进行分集合操作。判断相连的两个点是否在一个集合中不在答案就++，最后求出所有情况下的最大值即为答案。

废话说多了上代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 1e5 + 7;

int u[maxn], v[maxn], vis[maxn];
int main (){
    int T, cnt = 1;
    scanf ("%d", &T);
    while (T -- ){
        int n, m;
        scanf ("%d%d", &n, &m);
        for (int i = 0; i < m; i ++ )
            scanf ("%d%d", &u[i], &v[i]);
        int ans = 0;
        for (int i = 0; i < (1 << n); i ++ ){
            //cout << i << endl;
            for (int j = 0; j < n; j ++ )
                vis[j] = (i>>j&1);
            int sum = 0;
            for (int j = 0; j < m; j ++ )
                if (vis[u[j]] != vis[v[j]]) sum ++;
            ans = max(ans, sum);
        }
        printf ("Case #%d: %d\n", cnt ++, ans);
    }
}