hdu 4888 Redraw Beautiful Drawings(最大流，判环)
加入一个源点与汇点，建图例如以下：1. 源点 -> 每一行相应的点，流量限制为该行的和2. 每一行相应的点 -> 每一列相应的点，流量限制为 K3. 每一列相应的点 -> 汇点，流量限制为该列的和求一遍最大流，若最大流与矩阵之和相等，说明有解，，否则无解。推断唯一解，是推断残量网络...
BZOJ 3546 Life of the Party （二分图匹配-最大流）
题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3546题意：给定一个二分图。（AB两个集合的点为n，m），边有K个。问去掉哪些点后最大匹配会减少。思路：首先建图跑最大流。然后从s开始dfs一次，若能跑到B集合中的点x，那么说明x可以...
POJ2455Secret Milking Machine[最大流 无向图 二分答案]
SecretMilkingMachineTimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:11865 Accepted:3445DescriptionFarmerJohnisconstructinganewmilkingmachineandwis...
POJPower Network (最大流)
题目链接。分析：这题描述的可不是一般的复杂.其时就是很多源点、很多汇点，使尽量多流量的到达汇点。因为有很多源点，就再设一个源点（0号），使得0号到其它源点的容量为其它源点的初始量，同样设一汇点（n+1），使得其它汇点到该汇点的容量为其它汇点的初始量，如此就把很多的源点和汇点看成普通的点，单源单汇最大...
CCF 201703-5 引水入城（最大流问题：EK算法，BFS 50分）（Dinic算法 40分）
问题描述MF城建立在一片高原上。由于城市唯一的水源是位于河谷地带的湖中，人们在坡地上修筑了一片网格状的抽水水管，以将湖水抽入城市。如下图所示：这片管网由n行m列节点（红色，图中n=5，m=6），横向管道（紫色）和纵向管道（橙色）构成。行和列分别用1到n的整数和1到m的整数表示。第1行的任何一个节点均...
BZOJ 1711 吃饭dining/Luogu P1402 酒店之王 拆点+最大流流匹配
题意：（吃饭dining）有F种食物和D种饮料，每种食物或饮料只能供一头牛享用，且每头牛只享用一种食物和一种饮料。现在有n头牛，每头牛都有自己喜欢的食物种类列表和饮料种类列表，问最多能使几头牛同时享用到自己喜欢的食物和饮料。（1<=f<=100,1<=d<=100,1<...
POJ 2455 Secret Milking Machine (二分 + 最大流)
题目大意：给出一张无向图，找出T条从1..N的路径，互不重复，求走过的所有边中的最大值最小是多少。算法讨论：首先最大值最小就提醒我们用二分，每次二分一个最大值，然后重新构图，把那些边权符合要求的边加入新图，在新图上跑网络流。这题有许多注意的地方：1、因为是无向图，所以我们在加正向边和反向边的时候，流...
matlab实现图割算法中的最大流最小割Max-flow/min-cut问题（一）
本篇主要介绍matlab实现Max-flow/min-cut的方法，介绍一种只实现了Max-flow/min-cut的工具箱Bk_matlab。一：最大流最小割的由来 了解这个问题之前先说说这个问题的由来吧。最大流最小割最开始从图论的相关概念中引用过来，讲述一个带有起点与终点并且具有边权值的网络图中...
Escape(状态压缩+最大流，好题)
Escapehttp://acm.hdu.edu.cn/showproblem.php?pid=3605TimeLimit:4000/2000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):1320...
POJ 2516 Minimum Cost [最小费用最大流]
题意略；思路：这题比较坑的地方是把每种货物单独建图分开算就ok了。#include<stdio.h>#include<queue>#defineMAXN500#defineMAXM10002*4#defineINF10000000usingnamespacestd;//起点编...
hdu4975 A simple Gaussian elimination problem.（正确解法 最大流+删边判环）（Updated 2014-10-16)
这题标程是错的，网上很多题解也是错的。http://acm.hdu.edu.cn/showproblem.php?pid=49752014Multi-UniversityTrainingContest10AsimpleGaussianeliminationproblem.TimeLimit:2000...
HDU 3416 Marriage Match IV （求最短路的条数，最大流）
MarriageMatchIV题目链接：http://acm.hust.edu.cn/vjudge/contest/122685#problem/QDescriptionDonotsincerenon-interference。Likethatshow,nowstarvaealsotakeparti...
HDOJ 2448 - Mining Station on the Sea 构图最小费用最大流..阅读理解..
题意: 有M个station..有N个port以及N个船...现在每艘船都在某些station上..它们要回到port...保证存在可行方案..现在给出某个station存在航道的距离..以及某些port和stadion间的航道的距离...边是双向的..但一...
ZOJ 3229 Shoot the Bullet(有源汇上下界最大流)
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3442题目大意：一个屌丝给m个女神拍照，计划拍照n天，每一天屌丝给给定的C个女神拍照，每天拍照数不能超过D张，而且给每个女神i拍照有数量限制[Li，Ri]，对于每个女神n...
BZOJ1449[JSOI2009]球队收益&BZOJ2895球队预算——最小费用最大流
题目描述输入输出一个整数表示联盟里所有球队收益之和的最小值。样例输入331021111010133122331样例输出43提示 要求总费用最低考虑最小费用最大流。对于一场比赛同时决策两支队伍谁输谁赢不好办，我们先假设剩下的比赛每支队伍都输了，这样每次只要决策谁赢了即可。对于每次比赛将源点连向比赛，流...
hdu 4411 2012杭州赛区网络赛 最小费用最大流 ***
题意：有n+1个城市编号0..n，有m条无向边，在０城市有个警察总部，最多可以派出ｋ个逮捕队伍，在１..n每个城市有一个犯罪团伙， 每个逮捕队伍在每个城市可以选择抓或不抓，如果抓了第i 个城市的犯罪团伙，第i-1个城市的犯罪团伙就知道了消息 ，如果第i-1的犯罪团伙之前没有被抓，任务...
POJ 1273 Drainage Ditches | 最大流模板
#include<cstdio>#include<algorithm>#include<cstring>#include<queue>#defineN250#defineM250#defineINF100000000usingnamespacestd;...
POJ 1273 - Drainage Ditches - [最大流模板题] - [EK算法模板][Dinic算法模板 - 邻接表型]
题目链接：http://poj.org/problem?id=1273TimeLimit:1000MSMemoryLimit:10000KDescriptionEverytimeitrainsonFarmerJohn'sfields,apondformsoverBessie'sfavoriteclo...
POJ 1273 Drainage Ditches (网络最大流)
http://poj.org/problem?id=1273DrainageDitchesTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 55235 Accepted: 21104DescriptionEverytimeitrainson...
「网络流24题」「LuoguP2774」方格取数问题（最大流 最小割
Description在一个有m*n个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。Input第1行有2个正整数m和n，分别表示棋盘的行数和列数。接下来...