最长路是NP的：https://en.wikipedia.org/wiki/Longest_path_problem

如果最大费用最大流是多项式可解的，那可以把图的每个点分成一个入点一个出点，然后入点和出点之间建一条费用为0容量为1的边，就可以保证每个点只走一次．然后把源点流量限制为1，跑一个最大费用最大流就可以求出最长路了．那这不就证明了最长路是多项式可解的吗？

是不是可以发paper了