Color Graph

题意：

给了 \(n\) 个点和 \(m\) 条无向边，让你给边涂红色，要求奇数环不能全为红色。求最多可以给多少边涂红色，求出最大数量。
传送门

分析：

二分图的一个等价定义：不含有含奇数条边的环的图。
二分图性质：如果一个图不存在奇数环，那么一定是一个二分图。
因此，我们只要寻找到最多边数的二分即可。以子集枚举的方式，枚举哪些边属于二分图的左边，标记为 \(1\)，其余为 \(0\)。然后，枚举所有的边，把端点不属于同一边的边计数。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[150],b[150];
int vis[20];
int main()
{
    int t,n,m,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        int ans=0;
        scanf("%d%d",&n,&m);
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=m;i++)
            scanf("%d%d",&a[i],&b[i]);
        printf("Case #%d: ",++cas);
        for(int i=1;i<(1<<n);i++)
        {
            for(int j=0;j<n;j++)
            {
                if((i>>j)&1)
                    vis[j]=1;
                else
                    vis[j]=0;
            }
            int cnt=0+

            for(int j=1;j<=m;j++)
            {
                if(vis[a[j]]!=vis[b[j]])
                    cnt++;
            }
            ans=max(cnt,ans);
        }
        printf("%d\n",ans);
    }
    return 0;
}