hzwer.com _ Home | http://hzwer.com

« 上一页下一页 »Current position : 首页 >> 图论 >> 第15页

• 「BZOJ1097」[POI2007] 旅游景点atr

  

  DescriptionFGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸，他希望在满足他的要求的情况下，旅行的距离尽量短，这样他就有足...
  02014年10月19日5,402dijkstra,状压动规

• 「codecomb2092」课程选择

  

  题目描述大学选课总是烦恼着很多人。现在X同学选出了很多备选课，但是有的课程之间是有时间冲突的。X不会分身，自然无法在同一个时间上不同的课。每个课可能有很多备选时间，但是每个课只需要选一个时间上就可以了。当然X没有必要在不同时间上相同的课。           现在把X的备选课及相应的上课时间告诉你，请你求出X一星期最多可以上多少课。输入格式第一行输入一个n，表示X将提供给你n个备选课。接下来n行，每行...
  02014年10月13日2,697最大流

• 「codecomb2091」路径数量

  

  题目描述           给定一张n个点的有向图，求从点1到点n最多有多少条不相交的简单路径。所谓不相交即不经过相同的边的路径。输入格式第一行读入一个n，m，表示共n个点，m条边。接下来m行，每行两个整数x，y，表示从x到y有一条有向边。输出格式输出仅包括一行，即最多有多少条不相交的简单路劲。样例数据1输入4712122323233434输出2备注对于20%的数据n<=10，m<=1000；对于100%的数据n<=1000，m<=100000；题...
  02014年10月13日3,137最大流

• 「codecomb2090」最小乘积路

  

  题目描述给定n个点的带权有向图，求从1到n的路径中边权之积最小的简单路径。输入格式第一行读入两个整数n，m，表示共n个点m条边。接下来m行，每行三个正整数x，y，z，表示点x到点y有一条边权为z的边。输出格式输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此输出它模9987的余数即可。样例数据1输入331232331310输出9备注对于20%的数据，n<=10。对于100%的数据，n<=1000，m<=1000000。边权不超过10000。题...
  02014年10月13日3,495dijkstra

• 「BZOJ1023」[SHOI2008] cactus仙人掌图

  

  Description如果某个无向连通图的任意一条边至多只出现在一条简单回路（simplecycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也...
  22014年10月10日10,459递推与动规,单调队列,仙人掌

• 「BZOJ2324」[ZJOI2011] 营救皮卡丘

  

  Description皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。由于火箭队的重重布防，要想摧毁K号据点，必须按照顺序先摧...
  02014年10月9日7,573费用流,floyd

• 「BZOJ1093」[ZJOI2007] 最大半连通子图

  

  DescriptionInput第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。接下来M行，每行两个正整数a,b，表示一条有向边(a,b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。Output应包含两行，第一行包含一个整数K。第二行包含整数CModX.SampleInput6620070603122113245664SampleOutput33HINT对于100%的数据，N≤100000,M≤1000000；对于100%的数据，X≤...
  22014年10月8日7,486递推与动规,拓扑排序,图的连通

• 「NOIP模拟赛」祖孙询问

  

  「问题描述」已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。「输入格式」输入第一行包括一个整数n表示节点个数。接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1，那么a就是树的根。第n+2行是一个整数m表示询问个数。接下来m行，每行两个正整数x和y。「输出格式」对于每一个询问，输出1:如果x是y的祖先，输出2:如果y是x的祖先，否则输出0。「样例输入」10234-1122341323...
  02014年10月6日4,464最近公共祖先

• 「BZOJ3389」[Usaco2004 Dec] Cleaning Shifts安排值班

  

  Description    一天有T(1≤T≤10^6)个时段．约翰正打算安排他的N(1≤N≤25000)只奶牛来值班，打扫打扫牛棚卫生．每只奶牛都有自己的空闲时间段[Si，Ei](1≤Si≤Ei≤T)，只能把空闲的奶牛安排出来值班．而且，每个时间段必需有奶牛在值班．  那么，最少需要动用多少奶牛参与值班呢？如果没有办法安排出合理的方案，就输出-1.Input    第1行：N，T．    第2到N+1行：Si，Ei．Output    最少安排...
  32014年10月1日3,383dijkstra

• 「BZOJ3714」[PA2014] Kuglarz

  

  Description魔术师的桌子上有n个杯子排成一行，编号为1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费c_ij元，魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？Input第一行一个整数n(1<=n<=2000)。第i+1行(1<=i<=n)有n+1-i个整数，表示每一种询问所需的花费。其中c_ij（对区间[...
  52014年9月28日4,442prim

• 「NOIP模拟赛」交通

  

  黄金大神国的首都位于hzwer河中的一座岛屿。一道上班的时候，成千上万辆汽车通过岛屿从西岸的住宅区（由桥连接岛的西部）到东岸的工业区（由桥连接岛的东部）。该岛类似于矩形，它的边平行于主方向。故可将它看作是笛卡尔坐标系中的一个A*B的矩形，它的对角分别为（0,0）和（A,B）。岛上有n个交通节点（后宫建筑），编号为1…n，第i个节点坐标为(xi,yi)。如果一个节点的坐标为(0,y)，它就位于岛的西岸。类似的，坐标为(A,y)的...
  02014年9月27日3,734树形动规,图的连通

• 「BZOJ3697」「FJ2014集训」采药人的路径

  

  Description采药人的药田是一个树状结构，每条路径上都种植着同种药材。采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到...
  92014年9月26日8,789点分治