最小割 - Page 3

「BZOJ2132」圈地计划
Description最近房地产商GDOI(GroupofDumbbellsOrIdiots)从NOI(NutsOldIdiots)手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第i行第j列的区域，建造商业区将得到Aij收益，建造工业区将得到Bij收益。另外不同的区域连在一起...
02014年3月31日6,330最小割

「BZOJ1934」[SHOI2007] Vote 善意的投票
Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？Input第一行只有两个整数n，m，保证有2...
22014年3月17日4,725最小割
「BZOJ1412」[ZJOI2009] 狼和羊的故事
Description“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．”Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。...
02014年3月16日6,387最小割
「网络流24题」最小路径覆盖问题
Description问题描述：给定有向图G=(V,E)。设P是G的一个简单路（顶点不相交）的集合。如果V中每个顶点恰好在P的一条路上，则称P是G的一个路径覆盖。P中路径可以从V的任何一个顶点开始，长度也是任意的，特别地，可以为0。G的最小路径覆盖是G的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图G的最小路径覆盖。编程任务：对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。InputFormat文...
02014年2月28日8,951最小割
「CODEVS1907」方格取数3
题目描述 Description«问题描述：在一个有m*n个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。«编程任务：对于给定的方格棋盘，按照取数要求编程找出总和最大的数。输入描述 InputDescription第1行有2个正整数m和n，分别表示棋盘的行数和列数。接下来的m行，每行有n个正整数，表示棋盘方格中的数。输出描述 OutputDesc...
02014年2月20日4,480最小割
无聊写的A+B问题。。。
输入A,B输出A+B[crayon-661df93824b83670748244/]
42014年2月3日8,615最小割,spfa,kruskal,背包动规,线段树,floyd,树状数组
「CODEVS1922」骑士共存问题
题目描述 Description在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。输入描述 InputDescription第一行有2个正整数n和m(1<=n<=200,0<=m<n^2)，分别表示棋盘的大小和障碍数。接下来的m行给出障碍的位置。每行2个正整数，表示障碍的方格...
02014年2月2日4,677最小割
「JoyOI1338」QQ农场
背景BackgroundSandytea前段时间沉迷于QQ农场中……一天夜里，他梦见来到好友X的农场上……描述Description这个农场和游戏中略有不同。土地实际上是一个边长为N的正方形，由N*N块土地组成。在每块土地上，都种有一种农作物。如果他选择摘取一块土地上的农作物，就能获得一个固定的利润(当然，这个利润是正数)。不同土地上的利润多半是不同的。贪心的Sandytea本想摘取所有土地上的农作物。但是正当他准备行动时，却被告知...
02014年1月28日2,868最小割
「CODEVS1022」覆盖
题目描述 Description有一个N×M的单位方格中，其中有些方格是水塘，其他方格是陆地。如果要用1×2的矩阵区覆盖（覆盖过程不容许有任何部分重叠）这个陆地，那么最多可以覆盖多少陆地面积。输入描述 InputDescription输入文件的第一行是两个整数N，M (1<=N，M<=100)，第二行为一个整数K(K<=50)，接下来的K行，每行两个整数X，Y表示K个水塘的行列位置。(1<=X<=N，1<=Y<=M)。输出描述 ...
02014年1月26日4,177最小割
NOI2006最大获利
题目描述 Description新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一...
42014年1月18日6,556最小割
「网络流24题」搭配飞行员(飞行员配对方案问题)
「问题描述」飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。如图，假设有10个驾驶员，如图中的V1，V2，…，V10就代表达10个驾驶员,其中V1，V2，V3，V4，V5是正驾驶员,V6，V7，V8，V9，V10是副驾驶员。如果一个正驾驶员和...
22014年1月10日6,705最小割
「BZOJ1001」[BJ2006] 狼抓兔子
Description现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路1:(x,y)<==>(x+1,y)2:(x,y)<==>(x,y+1)3:(x,y)<==>(x+1,y+1)道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的.左上角和右下角为...
32014年1月9日26,025最小割,spfa