网络流 - Page 2

「FJ2015集训」贪吃蛇
最近lwher迷上了贪吃蛇游戏，在玩了几天却从未占满全地图的情况下，他不得不承认自己是一个弱菜，只能改去开发一款更弱的贪吃蛇游戏。在开发的过程中，lwher脑洞大开，搞了一个多条蛇的模式。但由于这种模式太难操作，于是他只好改变游戏的玩法，稍微变化一下游戏目标。新的游戏是这样的：一些蛇覆盖了一个网格。每个格子要么是一个障碍物，要么是蛇的一部分。每条蛇占据了一条折线(拐角处只能水平和竖直连接)，且只是占据两个格子...
62015年7月13日7,769费用流,有上下界网络流,随机化

「BZOJ4205」「FJ2015集训」卡牌配对
卡牌配对「问题描述」现在有一种卡牌游戏，每张卡牌上有三个属性值：A,B,C。把卡牌分为X,Y两类，分别有n1,n2张。两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。比如一张X类卡牌属性值分别是225,233,101，一张Y类卡牌属性值分别为115,466,99。那么这两张牌是可以配对的，因为只有101和99一组属性互质。游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。「输...
32015年7月5日6,028二分图匹配,网络流
「BZOJ3308」九月的咖啡店
Description深绘里在九份开了一家咖啡让，如何调配咖啡民了她每天的头等大事我们假设她有N种原料，第i种原料编号为i,调配一杯咖啡则需要在这里若干种兑在一起。不过有些原料不能同时在一杯中，如果两个编号为i,j的原料，当且仅当i与j互质时，才能兑在同一杯中。现在想知道，如果用这N种原料来调同一杯咖啡，使用的原料编号之和最大可为多少。Input一个数字NOutput如题SampleInput10SampleOutput30HINT1<=N<=2...
62015年6月2日6,623费用流
「CF546X」Codeforces Round #304 (Div. 2)
A.SoldierandBananas模拟[crayon-6908248680774766470907/]B.SoldierandBadges排序[crayon-690824868077c557185576/]C.SoldierandCards暴力模拟个一百万次。。。[crayon-6908248680781926664741/]D.SoldierandNumberGame用筛法得出每个数质因子个数前缀和即可[crayon-6908248680785657445866/]E.SoldierandTraveling我比较愚蠢写了网络流。。正解是什么我不知道[crayon-690824868078a891130790/] ...
52015年5月23日4,881模拟,筛法,网络流
POJ训练记录
1966.CableTVNetwork枚举源汇求最小割[crayon-69082486812c6671759764/]2386.LakeCounting搜索[crayon-69082486812d3301447183/]3863.BusinessCenter枚举每个电梯，二分求最小值[crayon-69082486812d9157194368/]2504.Boundingbox求外心然后旋转n次得到多边形坐标精度弃坑。。[crayon-69082486812dd994633364/]3155.HardLife最大密度子图+方案分数规划[crayon-69082486812e3605960769/]4028.GCDGuessingGame贪心策...
02015年5月13日5,242最小割,贪心,深度搜索,二分法,几何
「BZOJ3996」[TJOI2015] 线性代数
Description给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得D=（A*B-C）*A^T最大。其中A^T为A的转置。输出DInput第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。Output输出最大的DSampleInput3121310123237SampleOutput2HINT 1<=N<=500题解倒腾下式子发现是...
02015年4月22日6,663最小割
「BZOJ3638 / 3272」Cf172 k – Maximum Subsequence Sum
Description给一列数，要求支持操作：1.修改某个数的值2.读入l,r,k，询问在[l,r]内选不相交的不超过k个子段，最大的和是多少。InputThefirstlinecontainsintegern(1 ≤ n ≤ 105),showinghowmanynumbersthesequencehas.Thenextlinecontainsnintegersa1, a2, ..., an(|ai| ≤ 500).Thethirdlinecontainsintegerm(1 ≤ m ≤ 105)—thenumberofqueries.Thenextmlinescontainthequeriesintheformat,giveninthestate...
22015年4月16日5,336费用流,线段树
「BZOJ3931」[CQOI2015] 网络吞吐量
题意即题解最短路+网络流1A了赞233[crayon-6908248682705508808819/]
82015年4月7日6,084STL,dijkstra,最大流
「BZOJ1797」[Ahoi2009] Mincut 最小割
DescriptionA,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i(1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：问题一...
62015年4月7日11,162最小割,图的连通
「BZOJ2095」[POI2010] Bridges
DescriptionYYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承...
02015年4月4日5,329最大流,二分法,欧拉图
「East!_XVI」九尾妖狐
Background某无良设计师伊泽瑞尔:刀妹太弱了,我们来增强阿狸吧。Description阿狸现在有N个技能,伊泽瑞尔要决定它们是AD技能还是AP技能。因为出装不同,所以当一个技能是AP时,阿狸的爆发增加ap_i,当一个技能是AD时,阿狸的爆发增加ad_i。有些技能配合可以打出伤害加成,这样阿狸的技能就可以被表示为一张无向图。当有关联的两个技能都是AD时,阿狸的爆发增加AD_i,当两个技能都是AP时,阿狸的爆发增加AP_i,当两个技能不...
02015年4月4日4,725最小割
「BZOJ3894」文理分科
Description 文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如果选择理科，将得到science[i][j]的满意值。2．如果第i行...
22015年3月25日8,359最小割