Ruins He's house

这题囧了，看完了题目和样例，非常兴奋的写了个 0-1 背包上去，发现 WA 了，后来仔细想想不对，要求的是最大的安全系数 (暂且这么认为 - -)，这样定义的方程最有比较大的变化。

做如下定义：

定义 $dp[i]$ 为抢了 $i$ 元钱的最大安全系数，注意初始化的时候 $dp[0] = 1$，其他的设置成没有访问过，这里为了好转移，我将除了 $dp[0]$ 之外的 $dp$ 元素置为 $-1$ 。转移很好想，就是如下这个方程：

1
2
3
4
5
6

for (int i = 0; i < n; i++) {
  for (int j = max_money; j >= w[i]; j--) {
    if (dp[j - w[i]] != -1) { dp[j]=max(dp[j],dp[j-w[i]]*p[i];
    }
  }
}

注意 $p_i$ 表示的安全系数，这样数据中输入的并不是，所以要记得转化

这样用 O (n^2) 的时间复杂度就可以搞定这道 dp 题。

本题是典型的最大流最小割模型，利用最大流等于最小割求解，将每个城市拆成两个点，之间连容量为 $w$ 的边，注意起点和终点连容量为无穷大的边，然后为了方便，起点连源，终点连汇，容量也为无穷大，城市之间连容量为无穷大的双向边，直接跑最大流即可。

这题是算法导论上的经典模型，将发电站看成源，用户看成汇，这样就形成了多源多汇网络流模型，直接加一个总的源汇即可。

源到发电站的容量为发电站的容量，用户到汇 的容量为用户容量，直接跑最大流即可。

常见的多限制匹配问题，每头牛需要选择一种食物和一种饮料，每种食物和饮料只能被一头牛选到，所以直接建图，分三部分，左边为所有的食物，和源连边，容量为 $1$，右边是饮料，和汇连边，容量为 $1$，为了达到每头牛都只能选择一种食物和饮料的目的，中间为牛，每头牛拆成两个点，两个点连边，容量为 $1$，点 $1$ 和食物连，点 $2$ 和饮料连，在这基础上直接跑最大流即可。

无意中看到这题，就切了一下，感觉这题很适合刚刚接触散列表和字符串处理的朋友，直接对字符串 hash 就可以了，用 map 暴力不知道能不能过，没有尝试过。