网络流 - Page 5

「NOIP模拟赛」花园的守护之神
题目描述看着正在被上古神兽们摧残的花园，花园的守护之神――小Bug同学泪流满面。然而，FZOI不相信眼泪，小bug与神兽们的战争将进行到底！通过google，小Bug得知，神兽们来自遥远的戈壁。为了扭转战局，小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂，由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie，而且可以...
32014年10月28日4,063STL,最小割,dijkstra

「vijos1891」学姐的逛街计划
描述doc最近太忙了,每天都有课.这不怕,doc可以请假不去上课.偏偏学校又有规定,任意连续n天中,不得请假超过k天.doc很忧伤,因为他还要陪学姐去逛街呢.后来,doc发现,如果自己哪一天智商更高一些,陪学姐逛街会得到更多的好感度.现在doc决定做一个实验来验证自己的猜想,他拜托小岛预测出了自己未来3n天中,每一天的智商.doc希望在之后的3n天中选出一些日子来陪学姐逛街,要求在不违反校规的情况下,陪学姐逛街的日子自己智商的总和最大.可是...
02014年10月25日4,378费用流
「BZOJ1520」[POI2006] Szk – Schools
DescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleInput5112311513255415103331SampleOutput9题解这个裸的费用流吧。。正好复习下zkw[crayon-6634673900cfe579044943/] ...
12014年10月20日4,140费用流
「codecomb2092」课程选择
题目描述大学选课总是烦恼着很多人。现在X同学选出了很多备选课，但是有的课程之间是有时间冲突的。X不会分身，自然无法在同一个时间上不同的课。每个课可能有很多备选时间，但是每个课只需要选一个时间上就可以了。当然X没有必要在不同时间上相同的课。现在把X的备选课及相应的上课时间告诉你，请你求出X一星期最多可以上多少课。输入格式第一行输入一个n，表示X将提供给你n个备选课。接下来n行，每行...
02014年10月13日2,587最大流
「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日2,992最大流
「BZOJ2324」[ZJOI2011] 营救皮卡丘
Description皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。由于火箭队的重重布防，要想摧毁K号据点，必须按照顺序先摧...
02014年10月9日7,133费用流,floyd
「BZOJ1324」Exca王者之剑
Description Input第一行给出数字N,M代表行列数.N,M均小于等于100下面N行M列用于描述数字矩阵Output输出最多可以拿到多少块宝石SampleInput221221SampleOutput4题解最小割[crayon-6634673901aa2621324209/] ...
02014年8月26日4,634最小割
「BZOJ3698」「FJ2014集训」XWW的难题
「问题描述」XWW是个影响力很大的人，他有很多的追随者。这些追随者都想要加入XWW教成为XWW的教徒。但是这并不容易，需要通过XWW的考核。XWW给你出了这么一个难题：XWW给你一个N*N的正实数矩阵A，满足XWW性。称一个N*N的矩阵满足XWW性当且仅当：（1）A[N][N]=0；（2）矩阵中每行的最后一个元素等于该行前N-1个数的和；（3）矩阵中每列的最后一个元素等于该列前N-1个数的和。现在你要给A中的数进...
12014年7月20日4,779有上下界网络流
「BZOJ2561」最小生成树
Description　给定一个边带正权的连通无向图G=(V,E)，其中N=|V|，M=|E|，N个点从1到N依次编号，给定三个正整数u，v，和L(u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？Input　　第一行包含用空格隔开的两个整数，分别为N和M；接下来M行，每行包含三个正整数u，v和w表示图G存在一条边权为w的边(u,v)。最后一行包含用...
12014年7月19日7,558最小割
「BZOJ3396」[Usaco2009 Jan] Total flow 水流
DescriptionInput第1行输入N，之后N行每行描述一条水管，前两个英文字母表示水管的两端（大小写字母是不一样的），后一个整数表示水管的流量，流量不会超过1000.Output一个整数，表示总流量．SampleInput5AB3BC3CD5DZ4BZ6SampleOutput3题解直接上网络流模板。。。似乎有小写字母[crayon-6634673902ab2238462522/] ...
02014年7月10日3,520最大流
「NOIP模拟赛」魔术球问题弱化版
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，…的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4根柱子上最多可放11个球。对于给定的n，计算在n根柱子上最多能放多少个球。输入描述第1行有1个正整数n，表示柱子数。输出描述一行表示可以放的最大球数4样例输出。样例输入11题目限制（...
02014年7月3日3,164二分法,最大流
「BZOJ3504」[CQOI2014] 危桥
DescriptionAlice和Bob居住在一个由N座岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路是双向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。Alice希望在岛屿al和a2之间往返an次（从al到a2再从a2到al算一次往返）。同时，Bob希望在岛屿bl和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问Alice和Bob能完成他们的愿望吗？Input本...
22014年6月21日5,147最大流