admin管理员组文章数量:1597474
HDUOJ 1054 Strategic Game
题目链接
Problem Description
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:
Sample 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)
Sample Output
1
2
这道题是二分图最小点覆盖,可能比较难看出来,套一个匈牙利算法的模板即可,AC代码如下:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1505;
vector<int>g[N];
int match[N],vis[N];
int n,k,x,y;
int found(int u){
for(int v:g[u]){
if(!vis[v]){
vis[v]=1;
if(!match[v] || (found(match[v]))){
match[v]=u;
return 1;
}
}
}
return 0;
}
void hungary(){
int ans=0;
fill(match,match+N,0);
for(int i=0;i<n;i++){
fill(vis,vis+N,0);
if(found(i)) ans++;
}
printf("%d\n",ans/2);
}
int main(){
while(~scanf("%d",&n)){
for(int i=0;i<n;i++) g[i].clear();
for(int i=0;i<n;i++){
scanf("%d:(%d)",&x,&k);
while(k--){
scanf("%d",&y);
g[x].push_back(y);
g[y].push_back(x);
}
}
hungary();
}
return 0;
}
版权声明:本文标题:HDUOJ 1054 Strategic Game 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1726364018a1067223.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论