hdu 1054 Strategic Game (二分匹配)
Strategic Game
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4697 Accepted Submission(s): 2125
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:
题意:求最少要多少个士兵站岗可使全部点都能观察得到。
因为是树形结构,每个点都会有一条边,最大匹配数即为题解(不证明了..)。
和 hdu1068 差不多,一样的模板,不过这题是求最大匹配数,匈牙利后结果除二即为解。
//234MS 280K 1166 B C++
#include<stdio.h>
#include<string.h>
#define N 1505
struct node{
int v;
int next;
}edge[*N];
int match[N];
int vis[N];
int head[N];
int n,edgenum;
void addedge(int u,int v)
{
edge[edgenum].v=v;
edge[edgenum].next=head[u];
head[u]=edgenum++;
}
int dfs(int x)
{
for(int i=head[x];i!=-;i=edge[i].next){
int v=edge[i].v;
if(!vis[v]){
vis[v]=;
if(match[v]==- || dfs(match[v])){
match[v]=x;
return ;
}
}
}
return ;
}
int hungary()
{
int ret=;
memset(match,-,sizeof(match));
for(int i=;i<n;i++){
memset(vis,,sizeof(vis));
ret+=dfs(i);
}
return ret;
}
int main(void)
{
int a,b,m;
while(scanf("%d",&n)!=EOF)
{
edgenum=;
memset(head,-,sizeof(head));
for(int i=;i<n;i++){
scanf("%d:(%d)",&a,&m);
while(m--){
scanf("%d",&b);
addedge(a,b);
addedge(b,a);
}
}
printf("%d\n",hungary()/);
}
return ;
}
最新文章
- ubuntu下安装JDK并搭建activeMQ
- 后台返回国标码,怎么转化为JSON
- JBOSS最大连接数配置和jvm内存配置
- (转)HTML5开发学习(2):本地存储之localStorage 、sessionStorage、globalStorage
- 利用Azure Automation实现云端自动化运维(3)
- Oracle 当前时间加减
- MongoDB的一些用法(转藏)
- incredibuild agent service is not running
- javaScript中的一些知识
- [array] leetCode-4-Median of Two Sorted Arrays-Hard
- Python+Selenium+PageObject
- php中$this->;的用法简单介绍
- APP前端易用性和UI测试
- 20165211 2017-2018-2 《Java程序设计》第2周学习总结
- Python matplot的使用(一)
- hdu2602 DP (01背包)
- 学习:List的扁平化 和 拼接
- NOIP 2005 校门外的树
- 解决linux-mysql 登录时,报异常:Access denied for user &#39;root&#39;@&#39;localhost&#39;
- XINCLUDE