HDU——T 1054 Strategic Game
http://acm.hdu.edu.cn/showproblem.php?pid=1054
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8510 Accepted Submission(s): 4096
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:
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)
2
#include <cstring>
#include <cstdio> const int N();
int n,sumedge,head[N];
struct Edge
{
int v,next;
Edge(int v=,int next=):v(v),next(next){}
}edge[];
inline void ins(int u,int v)
{
edge[++sumedge]=Edge(v,head[u]);
head[u]=sumedge;
edge[++sumedge]=Edge(u,head[v]);
head[v]=sumedge;
} int match[N];
bool vis[N];
bool find(int u)
{
for(int v,i=head[u];i;i=edge[i].next)
if(!vis[v=edge[i].v])
{
vis[v]=;
if(!match[v]||find(match[v]))
{
match[v]=u;
return true;
}
}
return false;
} inline void read(int &x)
{
x=; register char ch=getchar();
for(;ch>''||ch<'';) ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';
} int main()
{
for(;~scanf("%d",&n);)
{
int ans=;sumedge=;
for(int u,k,i=;i<n;i++)
{
read(u),read(k);
for(int v;k--;)
read(v),ins(u+,v+);
}
for(int i=;i<=n;i++)
{
if(find(i)) ans++;
memset(vis,,sizeof(vis));
}
memset(edge,,sizeof(edge));
memset(head,,sizeof(head));
memset(match,,sizeof(match));
printf("%d\n",ans>>);
}
return ;
}
最新文章
- python基础整理笔记(七)
- angularjs之browserTrigger
- SMTP协议--在cmd下利用bat命令行发送邮件
- SK-Learn使用NMF(非负矩阵分解)和LDA(隐含狄利克雷分布)进行话题抽取
- 批量修改Project视图中Prefab的名字
- 关于Java文件删除的操作
- Pigcms中WeixinAction的简略版流程
- MySQL linux二进制安装
- 25、Javascript 事件
- Go学习笔记(二):编写 HelloWorld 程序
- mysql查询字段值为数字
- js动弹特效
- BZOJ_3629_[JLOI2014]聪明的燕姿_dfs
- [UE4]Overlap Event 碰撞事件
- Scara机器人微分运动
- [CF1041F Ray in the tube][数学]
- 虚拟机安装ubuntu18.04及其srs服务器的搭建
- LeetCode121.买卖股票的最佳时机
- websocket之四:WebSocket 的鉴权授权方案
- Java并发编程(四)锁的使用(上)
热门文章
- mysql数据库优化原则
- 工具-VMWARE技巧-桥接连外网-WIN7
- nodejs-app.js
- 洛谷 U3346 A1-偶回文数
- HDU 4340
- HDU 1431
- wordpress迁移以及遇到的一些问题[mysql备份导入导出][固定链接404]
- FATAL ERROR in native method: JDWP No transports initialized, jvmtiError=AGENT_ERROR_TRANSPORT_INIT
- JMX学习笔记(一)-MBean
- 【IOI 2011】Race