拆点专题
poj 3422 有流量限制的最小费用流 反用求最大 + 拆点
题意： 给一个n*n（50 * 50） 的数字迷宫，从左上点开始走，走到右下点。 每次只能往右移一格，或者往下移一格。 每个格子，第一次到达时可以获得格子对应的数字作为奖励，再次到达则没有奖励。 问走k次这个迷宫，最大能获得多少奖励。 解析： 拆点，拿样例来说明： 3 2 1 2 3 0 2 1 1 4 2 3*3的数字迷宫，走两次最大能获得多少奖励。 将每个点拆成两个
HDU 3277Marriage Match III（二分+并查集+拆点+网络流之最大流）
题目地址：HDU 3277 这题跟这题的上一版建图方法差不多，只不过需要拆点。这个点拆的也很巧妙，既限制了流量，还只限制了一部分，以前一直以为拆点会全部限制，原来也可以用来分开限制，学习了。 建图方法为：建一源点与汇点，将女孩进行拆点，拆成i和i+n，将i与源点连边，权值为mid，将i与i+n连边，权值为k，再将男孩与汇点连边，权值为mid，这时可以配对的就将i与相应的男孩连边，权值为1，不能
2278. 企鹅游行（最大流，拆点）
活动 - AcWing 在南极附近的某个地方，一些企鹅正站在一些浮冰上。 作为群居动物，企鹅们喜欢聚在一起，因此，它们想在同一块浮冰上会合。 企鹅们不想淋湿自己，所以它们只能利用自己有限的跳跃能力，在一块块浮冰之间跳跃移动，从而聚在一起。 但是，最近的温度很高，浮冰上也有了裂纹。 每当企鹅在一块浮冰上发力跳到另一块浮冰上时，起跳的浮冰都会遭到破坏，落点的浮冰并不会因此受到影响。 当浮冰
2240. 餐饮（最大流，拆点）
活动 - AcWing 奶牛们在吃饭方面十分挑剔。 每头奶牛都有自己喜欢的食物和饮料，并且不会食用其他不喜欢的食物和饮料。 农夫约翰为他的奶牛们做了美味的饭菜，但他忘了对照他们的喜好来检查菜单。 虽然他可能无法令所有奶牛满意，但他想给尽可能多的奶牛提供一顿完整的用餐----既有食物可吃，也有饮料可喝。 农夫约翰一共烹制了 F 种食物，并提供了 D 种饮料。 约翰共有 N 头奶牛，其中第
Cable TV Network UVA - 1660(网络流 拆点)
题意 n个点，然后给出m条边，然后问删至少多少个点可以得到不连通的图。 思路 不连通的图，把一个分成两个连通图是删点最少的情况，然后就联想到网络流最小割问题，最小割是删边，这个是删点，所以可以把一个点一切两开中间放一条边。然后任选一个点为起点，枚举其他的作为汇点，跑n-1次Dinic取最小值就行了。 代码 #include <bits/stdc++.h>using namespace
【HDU4560 2013西山居复赛D】【二分答案+网络流拆点】我是歌手 安排演唱会_每人歌不同_每场歌不同_人歌匹配一次
我是歌手 Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 350 Accepted Submission(s): 124 Problem Description 2013年一开始，一档音乐节目“我是歌手”就惊艳了大家一回。
P1345 [USACO5.4]奶牛的电信Telecowmunication（网络流+拆点）
地址：点击打开链接 总结： 拆点，顾名思义，就是把一个点拆成两个点。因为在网络流的模型中，割特指边集而非点集，所以想要实现“可以被割掉的点”，就用用到拆点思想。另外，这种方法也可以被理解为：使点同边一样有一个容量上限。把点A分成两个，一个叫A1，表示A的“入点”；另一个叫A2，表示A的“出点”。A的所有出边都从A2连出，所有入边都连向A1。再连一条边从A1指向A2，其边权为点A的“点容量”。
POJ 2391 Ombrophobic Bovines(二分+floyd+拆点+Dinic网络流)
题意：有n个田地，给出每个田地上初始的牛的数量和每个田地可以容纳的牛的数量。m条双向的路径，每条路径上可以同时通过的牛没有限制。 问牛要怎么走，能在最短时间内使得每块田地都能容纳的下，输出最短时间或-1。 分析：先floyd求出任意两点之间的最短距离，然后二分答案，判断是否可以在时间不超过mid的情况下完成移动： 建图： 每个点拆成两个点x（i）和x'(i+n)，源点向x连边，权值
poj 3422(拆点费用流)
题意：有个方阵，每个格子里都有一个非负数，从左上角走到右下角，每次走一步，只能往右或往下走，经过的数字拿走 每次都找可以拿到数字和最大的路径走，走k次，求最大和 如下图拆点 ， #include<cstdio>#include<cstring>#include<map>#include<vector>#include<cmath>#
拆点____ 行车路线
3255. 行车路线 小明和小芳出去乡村玩，小明负责开车，小芳来导航。 小芳将可能的道路分为大道和小道。 大道比较好走，每走 1 公里小明会增加 1 的疲劳度。 小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走 s 公里小明会增加 s^2 的疲劳度。 例如：有 5 个路口，1 号路口到 2 号路口为小道，2 号路口到 3 号路口为小道，3 号路口到 4 号路口为大道，4 号路口到 5
noip模拟赛多校第八场 T3 遥控机器人 （最短路 + 技巧拆点）
题面 简要题意： 给你一个 n n n 个点 m m m 条边的图。边 i i i 有颜色 c i c_i ci。你可以选择一些边改变它们的颜色成为区间 [ 1 , m ] [1, m] [1,m] 中的任意颜色，改变一条边 i i i 一次的代价是 w i w_i wi。询问你能否在一些改变操作后使得可以从 1 1 1 号点，每次只经过当前点的 特殊边
noip模拟赛多校第八场 T3 遥控机器人 （最短路 + 技巧拆点）
题面 简要题意： 给你一个 n n n 个点 m m m 条边的图。边 i i i 有颜色 c i c_i ci。你可以选择一些边改变它们的颜色成为区间 [ 1 , m ] [1, m] [1,m] 中的任意颜色，改变一条边 i i i 一次的代价是 w i w_i wi。询问你能否在一些改变操作后使得可以从 1 1 1 号点，每次只经过当前点的 特殊边
【uva 563】【构图】【最大流】【拆点】【n*m网格上l个点到边界线路不重合问题】
【题意】n*m网格上l个点到边界线路不重合问题 【思路】拆点，每个网格点拆为x,x' 有一个源点s（0）,汇点t(2*n*m+1) 主要是建图的思路： 1.x->x'(容量为1)，表示有一次机会过这个点 2.x'->上下左右四个入点，（容量为1），表示有一次机会走这个点
![【习题·图论】[JLOI2011]飞行路线：拆点最短路](https://img-blog.csdnimg.cn/20190211135447280.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JvbmFsZG83X1pZQg==,size_16,color_FFFFFF,t_70)
【习题·图论】[JLOI2011]飞行路线：拆点最短路
题目描述 Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n−1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。 Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多