观察题图可知，一个骑士能攻击到的格子与自己所在的格子异色，所以有一种摆法是都摆在同一颜色的格子上，把一条相互攻击的关系变为网络流路径，这样就将扔掉骑士转化为了求最小割

因为一个骑士能与多个骑士互相攻击，所以可以共用路径

建图如下：

·源点向每个黄格子连边，流量为1

·每个黄格子向能攻击到的红格子连边，流量为∞

·每个红格子向汇点连边，流量为1

跑最大流求出最少扔掉几个骑士，答案为n^2−m−maxflow

首先建立超源点和超汇点，源点与类型相连，试题与汇点相连，类型与对应试题相连

之后考虑边的容量

每种类型需要的试题有多道，所以源点与类型的边的容量应为该类型所需试题的数量

一道题只有一个，所以试题与汇点的边的容量为1，同理类型与试题的边的容量也为1

求最大流后进行判断，如果最大流等于m，那么寻找容量为0的边对应的类型和试题输出，否则无解

将每天拆成两个点，i点用于接收干净餐巾，i'点用于接收脏餐巾，那么：

·从i向T连流量为Ri，费用为0的边，如果满流则表示当天的餐巾数量足够

·从S向i'连流量为Ri，费用为0的边，表示每天结束时接收到Ri块脏餐巾

·从S向i连流量为∞，费用为p的边，表示每天开始时购买餐巾

·从i'向i+m连流量为∞，费用为f的边，表示送快洗

·从i'向i+n连流量为∞，费用为s的边，表示送慢洗

·从i'向(i+1)'连流量为∞，费用为0的边，表示将脏餐巾留到下一天

之后求最小费用最大流即可

本题求的是图中的环的平均值的最大值，可以发现这其实就是一个01分数规划，数据处理稍微有点麻烦

用map实现车次字符串与整数序号的对应，以每条线路的起始车次为边的起点，终止车次为终点，线路上的所有车次的速度和为权值建图，每次二分答案mid，在新图（即原图的每条边的权值都减去mid）中用spfa找正环。如果存在正环，l=mid；如果不存在，r=mid

最后一组数据会被卡，需要玄学优化，如果spfa中循环次数超过100000，直接返回存在正环的结果（当所有点的入队次数超过2n时，我们就认为图中有很大可能是存在负环/正环的）