图论 - Page 28 - hzwer.com

「POJ1062」昂贵的聘礼
题目描述 Description年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说：“嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。”探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他...
02014年2月24日5,190spfa

「BZOJ1877」[SDOI2009] 晨跑
DescriptionElaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发跑到学校，保证寝室编号为1，学校编号为N。Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的...
22014年2月23日5,357费用流
「BZOJ1015」[JSOI2008] 星球大战starwar
Description很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反...
32014年2月23日7,909并查集,离线处理
「BZOJ1066」[SCOI2007] 蜥蜴
Description在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同...
02014年2月22日7,099最大流
「CODEVS1913」数字梯形问题
题目描述 Description给定一个由n行数字组成的数字梯形如下图所示。梯形的第一行有m个数字。从梯形的顶部的m个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。规则1：从梯形的顶至底的m条路径互不相交。规则2：从梯形的顶至底的m条路径仅在数字结点处相交。规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交。对于给定的数字梯形，分别按照规则1，规则2，和规则3计算出从梯形的顶至底...
02014年2月21日3,979费用流
「BZOJ1834」[ZJOI2010] network 网络扩容
Description给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求：1、在不扩容的情况下，1到N的最大流；2、将1到N的最大流增加K所需的最小扩容费用。Input输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。Output输出文件一行包含两个整数，分别表示...
02014年2月21日7,851费用流,最大流
「CODEVS1033」蚯蚓的游戏问题
题目描述 Description在一块梯形田地上，一群蚯蚓在做收集食物游戏。蚯蚓们把梯形田地上的食物堆积整理如下：a(1,1) a(1,2)…a(1,m)a(2,1) a(2,2) a(2,3)…a(2,m) a(2,m+1)a(3,1) a(3,2) a(3,3)…a(3,m+1) a(3,m+2)……a(n,1) a(n,2) a(n,3)… a(n,m+n-1)它们把食物分成n行，第1行有m堆的食物，每堆的食物量分别是a(1,1),a(1,2),…,a(1,m)；第2行有m+1堆食物，每堆的食物量分别是a(2,1),a(2,2),...
02014年2月20日3,604费用流
「CODEVS1907」方格取数3
题目描述 Description«问题描述：在一个有m*n个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。«编程任务：对于给定的方格棋盘，按照取数要求编程找出总和最大的数。输入描述 InputDescription第1行有2个正整数m和n，分别表示棋盘的行数和列数。接下来的m行，每行有n个正整数，表示棋盘方格中的数。输出描述 OutputDesc...
02014年2月20日4,925最小割
「CODEVS1227」方格取数2
题目描述 Description给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大输入描述 InputDescription第一行两个数n,k（1<=n<=50, 0<=k<=10）接下来n行,每行n个数,分别表示矩阵的每个格子的数输出描述 OutputDescription一个数,为最大和...
12014年2月19日4,807费用流
「fjWC2014」生成树
Description给定一个无向图，要求图中一个生成树，这个生成树中的最大边和最小边相差最小，输出这个差值 Input每组测试数据一组样例每组样例首先输入两个整数n,m (3≤ n ≤ 300,0< m ≤ n*(n-1)/2)，表示该组样例中点和边的个数，之后每行三个整数x,y,s (0≤ x ≤ n-1,0≤ y ≤ n-1,1≤ s ≤ 10000)，表示编号为x和编号为y的点之间有一条长度为s的边相连，保证给定的图联通，任意两点之间只有一条边相连...
02014年2月16日14,295kruskal
「CODEVS1269」匈牙利游戏
题目描述DescriptionWelcometotheHungaryGames!ThestreetsofBudapestformatwistednetworkofone-waystreets.欢迎来到匈牙利游戏！布达佩斯（匈牙利首都）的街道形成了一个弯曲的单向网络。Youhavebeenforcedtojoinaraceaspartofa“RealityTV”showwhereyouracethroughthesestreets,startingattheSz´echenyithermalbath(sforshort)andendingattheTombofG¨ulBaba(tforshort).你被强制要求参加一个赛跑作为一个TV秀的...
02014年2月15日2,904spfa
「CF295B」Greg and Graph
Greghasaweigheddirectedgraph,consistingof n vertices.Inthisgraphanypairofdistinctverticeshasanedgebetweentheminbothdirections.Greglovesplayingwiththegraphandnowhehasinventedanewgame:Thegameconsistsof n steps.Onthe i-thstepGregremovesvertexnumber xi fromthegraph.AsGregremovesavertex,healsoremovesalltheedgesthatgoinandoutofthisvertex.Beforeexecutingeachstep,Gregwantstoknowthesumofle...
02014年2月14日4,287floyd,离线处理