UVALive 6432 Influence 搜索 剪枝大法好

有n个人,有k个人可以选作传播疾病的母体,和病人直接接触的未被感染者会被感染,求出选择k个人中的哪个可以取得最多的病人数目,有相同的取编号小的那个。

简单搜索,剪枝是如果一个同为母体的可以被其他母体直接或间接传染,这个母体就肯定不会是最多的那个,只会是一条分支。

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define PI acos(-1.0) #define MAXN 10100 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rtmaxm){ maxm = sum; ans = a[i]; } } } printf("%d\n",ans); } return 0; }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:POJ Drying
下一篇:ZOJ 3805 Machine
相关文章

NOIP 2014 D2T3 解方程 Hash大法好

poj 2828 Buy Tickets 万能的线

图文推荐
UVALive 6432 Influence 搜索 剪枝大法好
ZOJ 3640 Help Me
UVALive 6432 Influence 搜索 剪枝大法好
CF 518C(Anya and
UVALive 6432 Influence 搜索 剪枝大法好
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-08 人气:4
本文关键词:
分享到:

相关文章

  • ZOJ 3805 Machine 2012-07-22

    搜索.... Machine Time Limit: 2 Seconds Memory Limit: 65536 KB In a typical assembly line, machines are connected one by one. The first machine's output product will be the second machine's raw material. To simplify the problem, we put all machines into

  • UVALive - 3693 Balancing the Scale 2012-02-15

    题意:在给出的16个数中,求使得满足 x1* 4 + x2* 3 + x3* 2 + x4 = x5 + x6* 2 + x7* 3 + x8* 4 y1* 4 + y2* 3 + y3* 2 + y4 = y5 + y6* 2 + y7* 3 + y8* 4 这两个等式的个数有多少。 思路:状态枚举,先枚举四个数,然后查找是否有与这四个数组成的等式和的结果一样的组合,且这个组合与这四个数不相冲突,最后就是通过计算 st[i]*st[i^state]的总和就是,state表示全都有的状态 #in

  • UVALive 6622 Absurdistan Roads 2012-05-03

    题意: n(2000)个点的图 给出它的最短路矩阵 用n条边构造出满足最短路矩阵的图 保证图连通且解存在 思路: 我们可以先保证图连通 那么需要n-1条边 联想到是不是最小生成树?? 可以这样想 假设abc点已经连通 现在考虑再加入到连通块中一个点比如d 如果d-b的距离是d到abc三个点中最短的 那么这条边一定要被选 因为如果不选d-b 假设选了d-a 那么d-a已经长于d-b了 所以d-b的距离将不永远得不到满足 这样我们就可以根据最小生成树选出n-1条边了 还差一条 这时我们想知道最短路矩

  • UVALive - 3716 DNA Regions 2012-08-25

    题意:给出两个字符串,求出一个尽量长的序列使得有不超过p%的x满足Ax!=Bx 思路:首先明确条件是 (i-j)*p>=(sum[i]-sum[j])*100 => i*p-sum[i]*100 >= j*p-sum[j]*100, sum[i]表示前i个的不相等的个数,然后就是构造一个单调递减队列,储存结果,然后二分找出最小的j,第一个入队列的是一定是 #include #include #include #include #include using namespace s

  • UVALive - 3644 X-Plosives 2012-09-09

    题意:每个化合物都是有两种元素组成的,如果车上存在k个简单化合物时,如果它和已装车的化合物形成易燃物的话,你就应该拒绝装车,否则装车,输出没有装车的个数 思路:简单的并查集应用 #include #include #include #include using namespace std; const int MAXN = 100005; int f[MAXN]; int find(int x){ if (x != f[x]) f[x] = find(f[x]); return f[x]; }

  • UVALive 5103 Computer Virus on Planet Pandora Description 求模式串出现的种数 AC自动机 2012-09-29

    题目链接:点击打开链接 题意: case数 n个模式串 一个母串。 问:n个模式串出现的种数(一个模式串多次出现只算一次) 对于 "ABC" , 若母串出现了"CBA"这样的反串,也算出现了。 所以: 1 ABC CBA ans = 1 #include #include #include #include #include using namespace std; const int maxnode = 250*1000+10000; const int sigma_size = 26; st

  • UVALive - 3403 Mobile Computing 2013-01-01

    题意:给出房间的宽度r和s个挂钩的重量。设计一个尽量宽,但宽度不超过房间宽度的天平,挂着所有的挂钩。挂钩的宽度不计,且不相同的挂钩可以互相重叠 思路:每次将当前集合分成两个不相交的子集合,每次都构造出子集的最大的天平,最后从子集中选出最大的 #include #include #include #include #include using namespace std; const int MAXN = 65; double r,w[10],value[MAXN],ans; struct nod

  • UVALive - 3942 Remember the Word (Trie) 2013-05-07

    题意:给你一个有S个不同单词组成的字典和一个长字符串,把这个字符串分解成若干个单词的连接,有多少种方法 思路:转化为Trie树的形式储存,用d(i)表示字符从i开始的字符串的分解方案,每次搜索到一个单词末的时候就可以累加了 #include #include #include #include const int maxnode = 300001; const int sigma_size = 26; const int mod = 20071027; char str[maxnode]; in

  • UVALive 3027 Corporative Network 并查集水题 2013-06-21

    题意:有n个数进行,操作,'I'操作把a和b连接起来,而且a和b的距离即|a-b|%1000;'E'操作进行查询那个数到根节点的距离和;'O'操作结束。 没有压缩路径的并查集,所以我没有写递归函数直接循环。 由于E操作要的是a到根节点的距离和,计算时不需要取余,被坑了好几次。。。 代码: /* * Author: illuz * Blog: http://blog.csdn.net/hcbbt * File: uvalive3027.cpp * Create Date: 2013-12-05 2

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 1.214 (s). 10 q(s)