Mixed Integer Quadratic Programming

Sorry, I did not prove that this problem is in P. In other words, this problem may not be in P. But since I solved it, I believe it is not a problem that humans cannot solve.

흐즈로

Time limit: 3000 ms. Memory limit: 1024 MB.

You must solve a modified minimum cost maximum flow problem. The modified problem has the following conditions.

• The graph has $n$ vertices and $m$ directed edges. Vertex 1 is the source, and vertex $n$ is the sink. There are no multiple edges or self-loops.
• Each edge has a triple of integers $(a,b,c)$. It always holds that $0 \le a$, and there are at most 100 edges with $a \neq 0$.
• An edge with triple $(a_i,b_i,c_i)$ can carry up to $c_i$ units of resource. Sending $x$ units through it costs $a_i x^2+b_i x$. The cost can be negative.
• The amount of resource sent through each edge must be a non-negative integer.

The following conditions from the standard minimum cost maximum flow problem also apply.

• You must maximize the amount of resource sent from the source to the sink, and at the same time minimize the required cost.
• The amount leaving the source equals the amount entering the sink.
• For every vertex other than the source and the sink, the amount entering equals the amount leaving.

Given the graph that satisfies these conditions, write a program that solves the problem and prints the maximum flow and the minimum cost.

The first line contains two integers $n$ and $m$, separated by a space. ($2 \le n \le 200$, $1 \le m \le \min(n(n-1),1500)$)

From the second line onward, the next $m$ lines describe the edges. The $i$-th of these lines contains five integers $u_i$, $v_i$, $a_i$, $b_i$, $c_i$, separated by spaces. They describe a directed edge from $u_i$ to $v_i$ with triple $(a_i,b_i,c_i)$. ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le a_i \le 200$, $-200 \le b_i \le 200$, $1 \le c_i \le 10$)

It is guaranteed that at most 100 edges have $a_i \neq 0$. It is also guaranteed that there are no multiple edges and no self-loops.

Print two integers $f$ and $c$ on one line, separated by a space. $f$ is the maximum flow of the graph, and $c$ is the minimum cost that corresponds to the maximum flow. Note that the cost can be negative.