题意：
给出n点m边的简单无向图，每条边最开始是白色的。每一轮都可以将一条白边染成红色，要求最后不能有红色的奇环，求最多能够染的边数。
思路：
核心在于二分图的性质：二分图不存在长度为奇数的环，因为每一条边都是从一个集合走到另一个集合，必须要走奇数次。
这样的话问题就转化成了求最多可以选择多少条边使得选择出来的边为二分图。
可以看到n只有16，可以状压枚举所有情况，对于具体的每一种情况，如果该位为1的话，假设在左边集合里，否则在右边集合里。然后再枚举给出的m条边，如果端点的所在的集合不同，说明该边为二分图的一条边。最后取最大值即可。
总结：最重要的就是能够联想到二分图&看到数据范围想到可以状压枚举所有情况。
代码：
// Problem: Color Graph // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/4370/K // Memory Limit: 524288 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7; int n,m,vis[55]; PII e[55]; int main(){ int _=read,Case=1; while(_--){ int n=read,m=read; rep(i,1,m){ int u=read-1,v=read-1; e[i]={u,v}; } int ans=0; for(int i=0;i<(1<<n);i++){ for(int j=0;j<n;j++){ if(i&(1<<j)) vis[j]=1; else vis[j]=0; } int now=0; rep(i,1,m){ int u=e[i].first,v=e[i].second; if(vis[u]^vis[v]) now++; } ans=max(ans,now); } printf("Case #%d: %d\n",Case++,ans); } return 0; }
