尽管和普通的最短路不尽相同，本题仍然可以用$Dijkstra$算法的思路解决，所不同的是需进行逆推而非顺推。令$d[i]$表示进入结点$i$之后，至少要有$d[i]$单位的货物，到达目的地时货物数量才足够，则每次选择一个$d[i]$最小的未标号结点，更新它的所有前驱结点的$d$值即可算出所有的$d$值，然后在输出路径时根据$d$值可以直接构造字典序最小解。需要注意的是，$d[i]$可能会超过...
要想整个矩阵匹配，至少各行都得匹配。所以先把$P$的每行看做一个模式串构造出$AC$自动机，然后在$T$中的各行逐一匹配，找到$P$中每一行的所有匹配点。 只要在匹配时做一些附加的操作，就可以把匹配出来的单一的行拼成矩形。用一个$cnt[r][c]$表示$T$中以$(r,c)$为左上角、与$P$等大的矩形中有多少个完整的行和$P$对应位置的行完全相同。当$P$的第$i$行出现在$T$的第$...
本题模板多但长度短，而文本串又很长，正适合用$AC$自动机。一个容易忽略的地方是重复吹安的模板。如果模板有重复，后一个子串会覆盖前一个，因此需要用其他方法判重，其中一个简单的方法是建一个字符串到编号的索引$map<string,int> mp$，每次在初始化的时候清空，在插入的时候更新，最后在输出的时候使用。 代码如下：#include <bits/stdc++.h>...
使用二分法求解。对于一个猜测值$M$，只需要判断是否存在平均值小于$M$的回路。如何判断呢？假设存在一个包含$k$条边的回路，回路上各条边的权值为$w_1,w_2,...,w_k$，那么平均值小于$M$意味着$w_1+w_2+...+w_k<k*mid$即： 换句话说，只要把每条边$(a,b)$的权值$w(a,b)$变成$w(a,b)-M$，再判断新图中是否有负环即可。代码如下：...
因为商业线只能坐一站，所以可以枚举坐的是哪一站，比较所有可能性下的最优解。如果可以在$O(1)$的时间内计算出每种方案对应的最优方案，整个问题就可以在$O(K)$的时间内得到解决。 假设我们用商业线车票从车站$a$坐到车站$b$，则从起点到$a$、从$a$到终点这两部分路线对于“经济线网络”来说都应该是最短路。换句话说，我们只需要从起点开始、到终点结束坐两次单源最短路，记录下从起点到每一个...