Strategic Game HDU - 1054（二分图匹配+最小点覆盖）

72 阅读 0 评论 48 点赞

我是靠谱客的博主眯眯眼月饼，最近开发中收集的这篇文章主要介绍Strategic Game HDU - 1054（二分图匹配+最小点覆盖），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?

Your program should find the minimum number of soldiers that Bob has to put for a given tree.

The input file contains several data sets in text format. Each data set represents a tree with the following description:

the number of nodes
the description of each node in the following format
node_identifier:(number_of_roads) node_identifier1 node_identifier2 ... node_identifier
or
node_identifier:(0)

The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.

For example for the tree:

the solution is one soldier ( at the node 1).

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following table:

Input

4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

Output

1
2

鲍勃喜欢玩电脑游戏，尤其是战略游戏，但有时他找不到足够快的解决方案，然后他很伤心。现在他有以下问题。他必须保卫一座中世纪的城市，道路就像一棵树。他必须在节点上安置最少的士兵，这样他们才能观察到所有的边缘。你能帮助他吗?

您的程序应该找到Bob必须为给定树放置的最小士兵数。

输入文件包含几个文本格式的数据集。每个数据集代表一个树，描述如下:

节点数
以下列格式描述每个节点
node_identifier:(number_of_roads) node_identifier1 node_identifier2…node_identifier
或
node_identifier: (0)

对于n个节点(0 < n <= 1500)，节点标识符是0到n-1之间的整数。每条边在输入数据中只出现一次。

例如树:

解决方案是一个士兵(在节点1)。

输出应打印在标准输出上。对于每个给定的输入数据集，在一行中打印一个整数来给出结果(士兵的最小数量)。下表给出了一个例子:
输入
4
0:(1)1
1:(2)2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1)0
2:(0)
0:(0)
4:(0)
输出
1
2

实质就是一个最小点覆盖，最小点覆盖数=二分图最大匹配数

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n,used[1505],match[1505],Map[1505][1505];
bool Find(int x)
{
    for(int i=0;i<n;i++)
    {
        if(used[i]==0&&Map[x][i])
        {
            used[i]=1;
            if(match[i]==0||Find(match[i]))
            {
                match[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(match,0,sizeof(match));
        memset(Map,0,sizeof(Map));
        int a,b,c;
        for(int i=0;i<n;i++)
        {
            scanf("%d:(%d)",&a,&b);
            for(int i=0;i<b;i++)
            {
                scanf("%d",&c);
                Map[a][c]=1;
                Map[c][a]=1;
            }
        }
        int sum=0;
        for(int i=0;i<n;i++)
        {
            memset(used,0,sizeof(used));
            if(Find(i)) sum++;
        }
        printf("%dn",sum/2);
    }
}