hzwer.com - Page 119

「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日8,020费用流,最大流

「BZOJ2321」[BJ2011集训] 星器
DescriptionMagic Land上的时间又过了若干世纪…… 现在，人们谈论着一个传说：从前，他们的祖先来到了一个位于东方的岛屿，那里简直就是另外一个世界。善于分析与构造的Magic Land上的人们总是不明白那里的人们是如何不借助精确的实验与计算驱动和操纵魔法。偶然地，一个魔法使（Magician）来到了Magic Land，在临走的时候留下了一个神奇的盒子，叫做星器（Casket of star）。虽然不知道这个盒子是做什么...
02014年2月20日3,745其它
「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,707费用流
「CODEVS1907」方格取数3
题目描述 Description«问题描述：在一个有m*n个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。«编程任务：对于给定的方格棋盘，按照取数要求编程找出总和最大的数。输入描述 InputDescription第1行有2个正整数m和n，分别表示棋盘的行数和列数。接下来的m行，每行有n个正整数，表示棋盘方格中的数。输出描述 OutputDesc...
02014年2月20日5,053最小割
「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,870费用流
「BZOJ1067」[SCOI2007] 降雨量
Description我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。Input输入仅一行包含一个正整数n，为已知的数据。...
32014年2月19日9,312线段树
「fjWC2014」猜数字
DescriptionK国在胖哥的英明统治下，近来迷上了一款非常脑残的游戏，叫做猜数字，这个游戏是一个二人游戏，胖哥认为它非常有利于促进两个人之间的感情，假设玩家A和玩家B进行这个游戏，首先他们会确定一个正整数n，然后A从1-n中选定一个整数，注意一旦选定之后只有游戏结束都不能修改这个数字，假设这个数字是x，然后游戏开始，每次B都可以在1-n中选择一个整数，假设这个数字是y，然后A会告诉他gcd(x,y)的值，即x和y的最大公...
02014年2月16日3,546贪心
「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,373kruskal
「CODEVS1269」匈牙利游戏
题目描述DescriptionWelcometotheHungaryGames!ThestreetsofBudapestformatwistednetworkofone-waystreets.欢迎来到匈牙利游戏！布达佩斯（匈牙利首都）的街道形成了一个弯曲的单向网络。Youhavebeenforcedtojoinaraceaspartofa“RealityTV”showwhereyouracethroughthesestreets,startingattheSz´echenyithermalbath(sforshort)andendingattheTombofG¨ulBaba(tforshort).你被强制要求参加一个赛跑作为一个TV秀的...
02014年2月15日3,006spfa
「CODEVS1690」开关灯
题目描述Description YYX家门前的街上有N(2<=N<=100000)盏路灯，在晚上六点之前，这些路灯全是关着的，六点之后，会有M(2<=m<=100000)个人陆续按下开关，这些开关可以改变从第i盏灯到第j盏灯的状态，现在YYX想知道，从第x盏灯到第y盏灯中有多少是亮着的(1<=i,j,x,y<=N)输入描述InputDescription第1行:用空格隔开的两个整数N和M第2..M+1行:每行表示一个操作,有三个用空格分开的整数:指令号(0代...
02014年2月15日3,346线段树
「CODEVS1191」数轴染色
题目描述Description在一条数轴上有N个点，分别是1～N。一开始所有的点都被染成黑色。接着我们进行M次操作，第i次操作将[Li,Ri]这些点染成白色。请输出每个操作执行后剩余黑色点的个数。输入描述InputDescription输入一行为N和M。下面M行每行两个数Li、Ri输出描述OutputDescription输出M行，为每次操作后剩余黑色点的个数。样例输入SampleInput103335728样例输出SampleOutput963数据范围及提示DataSize&...
82014年2月15日3,541线段树
「fjWC2014」最短路
Description给定一个n个点m个边的有向图，所有边长度为1，现问对于每条边，设这条边从节点x出发指向节点y，将这条边从图中删除之后，x到y的最短路为多少Input首先输入一个整数Q(0 < Q ≤ 10)，表示有Q组样例每组样例首先输入两个整数n, m (0 < n ≤ 500, 0 < m ≤ 10000)，表示该组样例所表示的图中有n个点和m条有向边，之后m行，每行两个个整数x, y, (1 ≤ x, y ≤ n)，表示有一条编号为x的节...
02014年2月14日2,515广度搜索