Ural 1500Pass Licenses(状态压缩dfs)

有k种执照,n个点,m条路,每条路都属于一些执照(拥有指定执照才能走)

求从0走到1 最少需要多少执照

枚举 0到k-1 二进制的每一位代表是否拥有该执照,那么只用枚举状态0~(2^(k-1)-1)即可。表示执照是否存在的状态,然后就是dfs暴搜了,在搜的过程中,如果这个状态的需要执照个数>=可行解的最小值,那么不需要搜索,直接换另一种状态。详见代码:

#include #include #include using namespace std; int mp[35][35]; int visi[35]; int rans[35]; int n; void dfs(int p,int c) { visi[p]=1; if(p==1) return; for(int i=0;i>k>>n>>m) //n个结点,m条路,k种护照 { memset(mp,0,sizeof(mp)); while(m--) { scanf("%d%d%d",&a,&b,&c); mp[a][b]=(mp[a][b]|(1=2^20即可 int tmp,cnt,q; int res; //tmp记录状态 cnt记录最小的满足条件个数 for(i=0;i=ans的不要 { if(tmp&1) cnt++; tmp>>=1; } if(cnt>=ans) continue; tmp=q; memset(visi,0,sizeof(visi)); dfs(0,tmp); if(visi[1]) { ans=0; res=tmp; while(tmp) { if(tmp&1) ans++; tmp>>=1; } } } int t=0; q=0; while(res) { if(res&1) rans[t++]=q; res>>=1; q++; } cout

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:UVA 11714 - Blind Sorting(推理贪心)
下一篇:hdu3308 LCIS(线段树区间合并)
相关文章

ural 1165 subnumber ------猥琐的

Ural 1095 Nikifor 3 数论

URAL 1010 Discrete Function(解题

ural 1471 Tree题解

URAL 1806

Ural 1057(Amount of Degrees-数位

URAL 1136 Parliament 二叉树水题

URAL 1062 - Triathlon(半平面交)

URAL 1019 - Line Painting

URAL 1233 - Amusing Numbers

图文推荐
Ural 1500Pass Licenses(状态压缩dfs)
ZOJ 3640 Help Me
Ural 1500Pass Licenses(状态压缩dfs)
CF 518C(Anya and
Ural 1500Pass Licenses(状态压缩dfs)
hdu 1016 Prime R
UVA - 11987 - A

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

相关文章

  • URAL 1033 Labyrinth(DFS) 2012-10-10

    Administration of the labyrinth has decided to start a new season with new wallpapers. For this purpose they need a program to calculate the surface area of the walls inside the labyrinth. This job is just for you! The labyrinth is represented by a m

  • hdu3308 LCIS(线段树区间合并) 2014-05-21

    题目链接:hdu3308 /*hdu3308 LCIS 线段树区间合并 题目大意: 求一段区间内的连续最长 思路: 记录以区间左端点开始的LCIS,以区间右端点结尾的LCIS以及整个区间的LCIS, 区间左端点的数和区间右端点的数。 更新和建树操作都应更到叶子节点,只有叶子节点的信息时可以直接得出,然后 递归回到父节点,父节点可以根据左右孩子的信息来更新自己 */ #include #include #include #include #include using namespace std;

  • C++ - 虚继承(virtual inheritance) 2014-06-28

    虚继承(virtual inheritance) 本文地址: http://blog.csdn.net/caroline_wendy/article/details/18089215 虚继承主要是避免基类重复被继承, 包含多个相同基类, 导致歧义性, 使用虚基类(virtual base class)继承, 可以使派生对象只包含一份基类文件. 如果不使用虚继承, 则派生类需要提供一份自己的示例版本, 参见: http://blog.csdn.net/caroline_wendy/article/

  • POJ 1442 Black Box 2014-07-26

    题意: 给你个序列和一串询问 询问前a[i]个数字第i小的是几 思路: 动态的第k值问题 由于区间只增不减所以是水题 利用平衡树解决这类问题 treap是方便编写的类似平衡树的产品 treap方便实现BST的功能 splay更适合于去维护区间 代码: #include #include #include #include #include using namespace std; #define N 30010 #define inf ((1Uval[u]); res=insert(ch[u][

  • URAL 1183 Brackets Sequence 记忆化搜索 + DFS 2013-10-14

    这个烂题是昨天这个点开始看的. . . . . .然后卡到现在。 第一次做需要记录路径的题。大体可以想到是在记忆化搜索的回溯阶段确定那两个括号可以匹配,可就是写不出来啊。然后去问尚神怎么实现的(自从虎哥和崔老师走了之后,貌似只有尚神一个人可以问了. . . .),尚神说跟我的状态转移方程不一样。不过说了一下记录路径的思路,大体上还是差不多的。 寻找路径的两种方法,一种是在回溯过程中记录,另一种就是根据 dp[][]的值和状态转移方程从头找一遍。 第二种可能是因为又额外的DFS了一次效率要低好多。

  • Ural 1152 False Mirrors(状压DP) 2012-01-07

    题目地址:Ural 1152 初学状压DP,原来状压只是用到了个位运算。。 很水的状压DP。注意四则运算的优先级是高于位运算的。。也就是说如果既用到了四则运算,也用到了位运算,要想先算位运算的话,要将位运算加括号。因为这个地方调了好久。。 代码如下: #include #include #include #include #include #include #include #include #include #include #include using namespace std; cons

  • URAL 1748. The Most Complex Number 反素数 2014-05-11

    题目来源:URAL 1748. The Most Complex Number 题意:求一个小于等于n的因子最多的数 思路:搜索+剪枝 #include #include using namespace std; typedef unsigned __int64 LL; LL prime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; LL num, sum, n; void dfs(int p, int q, LL x, LL y) {

  • URAL 1018 Binary Apple Tree 简单树形背包 2014-12-08

    Description Let's imagine how apple tree looks in binary computer world. You're right, it looks just like a binary tree, i.e. any biparous branch splits up to exactly two new branches. We will enumerate by integers the root of binary apple tree, poin

  • Curling 2.0 (poj 3009 dfs) 2012-01-10

    Language: Default Curling 2.0 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 11954 Accepted: 5061 Description On Planet MM-21, after their Olympic games this year, curling is getting popular. But the rules are somewhat different from ours

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

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

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