ICPC2019上海区域赛 K-Color-Graph题解

柔光的暖阳◎ 2022-12-28 11:17 130阅读 0赞

### 文章目录 ###

*  题目描述（翻译版）
 *   *  输入描述
     *  输出描述
     *  输入
     *  输出
 *  算法分析
 *  解题代码
 *  错题分析
 *   *  二分图的概念

--------------------

链接：https://ac.nowcoder.com/acm/contest/4370/K  
来源：牛客网

# 题目描述（翻译版） #

给出一个简单的图形 `N` 个顶点和 `M` 条边。简单图是无向图，它没有自环（两端的边连接到同一顶点），并且在任何两个不同的顶点之间不超过一个边。最初，每个边缘都是白色。每回合，您都可以选择白色边缘并将其涂成红色。不允许您生成仅由红色边组成的奇数长的环。可以涂成红色的最大边数是多少？

## 输入描述 ##

> 输入的第一行给出了测试用例的数量，**T（1 ≤ T ≤ 30）**。随后是 **T** 测试用例。  
> 对于每种情况，第一行仅包含两个整数 **N** 和 **M** *（2 ≤ N ≤ 16 ，1 ≤ M ≤ Ñ(Ñ - 1) / 2）*\*。  
> 下一个的第 i 行 **M** 行描述第 i 个边：两个整数 **ü，v** 表示介于 **ü** 和 **v** 。保证没有自环和多个边。

## 输出描述 ##

> 对于每个测试用例，输出一行包含 **“ Case \#x：y”** 的行，其中 **x** 是测试用例编号（从1开始），**y** 是可以绘制为红色的最大边数。

## 输入 ##

2
    4 5
    1 2
    1 3
    1 4
    2 4
    3 4
    5 6
    1 2
    2 3
    3 1
    1 4
    4 5
    3 5

## 输出 ##

Case #1: 4
    Case #2: 5

# 算法分析 #

根据题目所说的：`不允许您生成仅由红色边组成的奇数长的环。可以涂成红色的最大边数是多少？`

也就是说要使得，最后红色的边形成的图中，不存在奇数长度的环。

\*\*\*二分图的性质：二分图中的所有环都是偶数长度，不存在奇数长度的环。\*\*\*

因此对于A集合中的情况进行枚举，那么B集合的情况也就唯一确定了，然后根据枚举的情况去寻找该情况下的最大边数，所有情况枚举完之后，取最大值即可。

# 解题代码 #

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxn=105;
    const int maxm=1e4+5;
    
    struct edge{
        
        int u,v;
    }E[maxm];	//记录边的内容
    
    int tot=0;	//记录边数
    
    void addedge(int u,int v){
        
        E[++tot].u=u;
        E[tot].v=v;
    }
    
    int color[maxn];	//用来标记点所在的集合，两个集合用 1｜0 标示
    
    int main(){
        
        int T;
        cin >> T;
        for(int kase = 1; kase <= T; kase++){
        
            int n,m;
            scanf("%d%d",&n,&m);
            fill(color, color+1+n, 0);
          
            tot = 0;
            for(int i = 1; i <= m; i++){
        
                int u,v;
                scanf("%d%d",&u,&v);
                addedge(u,v);
            }
          
          	//用于枚举二分图的所有情况，找出每种情况的最大值，就是最终结果
            int ans=0;
            for(int meijv = 0;meijv <= (1<<n) - 1; meijv++){
        
                int mj = meijv;
              	
              	//类似于二进制的操作，枚举四个位置的情况
             		//如 mj=0: 0000, mj=1: 1000, mj=2: 0100, mj=3: 1100 ......
                for(int i = 1; i <= n; i++){
        
                    if(mj & 1){
        
                        color[i]=1;
                    }
                    else color[i]=0;
                    mj >>= 1;
                }
              	//类似于二进制的操作，枚举四个位置的情况
              	
                int res=0;
                for(int i = 1; i <= tot; i++){
        
                  	//当边的起点和终点不在一个集合时，就证明这个边是二分图的边
                    if(color[E[i].u] != color[E[i].v]){
        
                        res++;
                    }
                }
              	
                ans = max(ans, res);
            }
          	//用于枚举二分图的所有情况，找出每种情况的最大值，就是最终结果
          
            printf("Case #%d: %d\n",kase,ans);
        }
    }

--------------------

# 错题分析 #

## 二分图的概念 ##

![8aKTO0.jpg][] ![二分图][8aK2TS.jpg]

[8aKTO0.jpg]: https://s1.ax1x.com/2020/03/17/8aKTO0.jpg
[8aK2TS.jpg]: https://s1.ax1x.com/2020/03/17/8aK2TS.jpg