注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[NBUT] 1182 Counter-Strike  

2012-07-11 19:02:41|  分类: NBUT 2012 Summer |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
  • 问题描述
  • Do you ever remember the classic game - Counter-Strike?

    STANMASH is a team member of a CS Team.
    Today his team is against another team.
    Before the starting, STANMASH, the leader of the team, decided to analyze the Combat Effectiveness of each team member. He found that - member A can kill someone in another team; member B can kill someone in another team, etc.
    So he made a list that who can kill whom. We assume that one member only can kill one enemy in that map.
    [NBUT]  1182 Counter-Strike - Minary - Minary_Acdream
     
    How many enemies can they kill in maximum? (We assume that STANMASH's team is larger than or the same as another's, but they can only let the same number as the enemy team member to play this match).
  • 输入
  • This problem contains several cases.
    The first line of each case is two integers N and M (1 <= M <= N <= 500), indicate the number of STANMASH team's members and another team's members.
    Then follow N lines. The first integer of ith line Ki indicates the number of enemies that ith team member can kill (0 <= Ki <= M). Then follow Ki integers, each integer is the ID of enemy that he can kill. (1 <= ID <= M)
  • 输出
  • For each case, you should output that the maximum number of enemies that they can kill.
  • 样例输入
  • 3 3 3 1 3 2 1 1 1 1 
  • 样例输出
  • 2 

    模板题,这是一道二分图的最大匹配的题目,直接套用模板就行了。
     A组 B组
     1 1
     2 2
     3 3

    下面是代码:

    #include<iostream>
    using namespace std;

    const int MAXN = 501; //一次WA是因为开了500
    bool map[MAXN][MAXN], vis[MAXN];
    int match[MAXN];
    int cnt = 0;
    /** 注意下标从1开始 */
    /**
    * map数组即一个连通性数组
    * vis数组是在某次找增广路的时候右边的某个点有没有被访问过
    * match数组即右边的点对应匹配左边的点的编号
    */

    bool dfs(int v, int n)
    {
    /** 枚举右边的点 */
    for(int i = 1; i <= n; i++)
    {
    /** 如果这次增广路寻找右边的这个点没被访问,且与左边的v连通 */
    if(!vis[i] && map[v][i])
    {
    vis[i] = true;

    /**
    * dfs(match[i], n):右边的i点的匹配顶点为match[i]
    * 说明这条边是匹配边,那么我们往下搜看看能不能完成增广路
    * 如果能完成增广路,则我们将i点的匹配顶点修改为v
    * 如果match[i]为0则说明i点是未被匹配的点
    * 那么将i点的匹配顶点修改为v
    * 这段代码完成了“匹配->未匹配”交替搜索
    */
    if(dfs(match[i], n) || !match[i])
    {
    match[i] = v;
    return true;
    }
    }
    }

    return false;
    }

    void max_match(int n, int m)
    {
    memset(match, 0, sizeof(match));
    cnt = 0;
    /** 枚举左边的点 */
    for(int i = 1; i <= n; i++)
    {
    /** 重新初始化vis */
    memset(vis, 0, sizeof(vis));

    /** 对左边的i点搜增广路 */
    if(dfs(i, m)) cnt++;

    }
    }

    int main()
    {
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
    memset(map,0,sizeof(map));
    memset(match,0,sizeof(match));
    for(int i = 1;i <= n;i ++)
    {
    int a;
    scanf("%d",&a);
    for(int j = 0;j < a;j ++)
    {
    int q;
    scanf("%d",&q);
    map[i][q] = 1;
    }
    }
    max_match(n, m);
    printf("%d\n", cnt);


    }


    }


       
  评论这张
 
阅读(60)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018