1、2006 飞行员配对(二分图最大匹配)
题意:每一架飞机都必须要有能够互相配合的英籍飞行员和外籍飞行员配合给出m个外籍飞行员,n-m个英籍飞行员以及能够互相配合的外籍和英籍飞行员,求最多能出动多少飞机
思路:二分图最大匹配。
2、1459 迷宫游戏(最短路变形)
思路:给出一个迷宫迷宫每个房間都有一个分数。现在需要在保证从起点到终点路径最短(消耗时间最少)的情形下使得经过的房间的分数总和最大。
思路:SPFA同时记錄分数的变化。
思路:由于数很大不再递推求,直接用黄金分割求做乘法模拟。