# 思路
首先想到费用流。
对于每个点拆点。然后考虑我们怎样才能保证每个点只被用一次。
如果$i$与$j$满足条件。那么就从$i$向$j$连一条边并且从$j$向$i$连一条边。这样每次增广的时候我们都可以看作某一条边被增广了两次。显然从$i$到$j$和从$j$到$i$的边是等价的。也就是说,如果当前增广这两个点之间的边更优秀,那么在增广完成从$i$到$j$和从$j$到$i$这两条边流量变为$0$之前不回去增广其他的边。
比较难解释,仔细想一下可以发现是对的。这样最后我们找出的流量实际上是答案的两倍。除二即可。
然后还要考虑题目中对于价值的限制。我们把价值当作费用,每次增广费用最大的路径。直到如果再增广费用变为负数为止。
# 代码
```cpp=
/*
* @Author: wxyww
* @Date: 2019-02-17 14:52:25
* @Last Modified time: 2019-02-17 19:36:45
*/
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 410,M = 1000000 + 100,INF = 1e9;
ll read() {
ll x=0,f=1;char c=getchar();
while(c'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&cq;
int S,T;
bool pd(int x,int y) {
if(x > 1);
return 0;
}
```
相关文章
- java中判断字符串是否为数字的方法的几种方法
- 5个缺失的 JavaScript 数字格式化函数
- 括号配对问题--nyoj-2(栈)
- 页面上有3个输入框:分别为max,min,num;三个按钮:分别为生成,排序,去重;在输入框输入三个数字后,先点击生成按钮,生成一个数组长度为num,值为max到min之间的随机整数点击排序,对当前数组进行排序,点击去重,对当前数组进行去重。 每次点击之后使结果显示在控制台
- oracle 重置序列从指定数字开始的方法详解
- 【python】获取列表中最长连续数字
- [转]字符型IP地址转换成数字IP的SQL函数
- Python基础一数据类型之数字类型
- Long.parseLong(String s) 其中s必须是数字形式的字符串,才能运用该函数转化为长整型。
- LeetCode 268. Missing Number (缺失的数字)