혼합 정수 이차 계획법

죄송합니다, 저는 이 문제가 P에 속하는지 증명하지 않았습니다. 다시 말해, 이 문제는 P에 속하지 않을 수도 있습니다. 하지만 적어도 제가 풀었으니, 인간이 풀 수 없는 문제는 아닐 거라고 생각합니다.

흐즈로

시간 제한은 3000 ms, 메모리 제한은 1024 MB입니다.

여러분은 이 문제에서 다음과 같이 변형된 최소 비용 최대 유량 문제를 해결해야 합니다. 변형된 문제의 조건은 다음과 같습니다.

• 그래프에는 $n$개의 정점과 $m$개의 방향 간선이 있습니다. 1번 정점은 시작점이고, $n$번 정점은 끝점입니다. 중복 간선이나 자기 자신을 향하는 간선은 없습니다.
• 각 간선에는 정수 세 개의 순서쌍 $(a,b,c)$가 있습니다. 항상 $0 \le a$이고, $a \neq 0$인 간선은 최대 100개입니다.
• 순서쌍 $(a_i,b_i,c_i)$를 갖는 간선으로는 최대 $c_i$단위의 자원을 보낼 수 있습니다. $x$단위의 자원을 보내면 $a_i x^2+b_i x$의 비용이 듭니다. 비용은 음수가 될 수 있습니다.
• 각 간선으로 보내는 자원의 양은 음이 아닌 정수여야 합니다.

기본적인 최소 비용 최대 유량 문제와 같은 조건도 적용됩니다.

• 시작점에서 끝점으로 보내는 자원의 양을 최대화하면서, 동시에 요구되는 비용을 최소화해야 합니다.
• 시작점에서 나가는 자원의 양과 끝점으로 들어오는 자원의 양은 같습니다.
• 시작점과 끝점을 제외한 모든 정점에서 들어오는 자원의 양과 나가는 자원의 양은 같습니다.

주어진 조건에 맞는 그래프가 주어졌을 때, 문제를 해결하고 최대 유량과 최소 비용을 출력하는 프로그램을 작성하세요.

첫 줄에 정점의 개수 $n$과 간선의 개수 $m$이 공백으로 구분되어 주어집니다. ($2 \le n \le 200$, $1 \le m \le \min(n(n-1),1500)$)

두 번째 줄부터 $m$개의 줄에 걸쳐 간선 정보가 주어집니다. $i$번째 줄에는 $i$번째 간선에 관한 정수 5개 $u_i$, $v_i$, $a_i$, $b_i$, $c_i$가 공백으로 구분되어 주어집니다. 이는 순서쌍 $(a_i,b_i,c_i)$를 가지며 $u_i$에서 $v_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$)

$a_i \neq 0$인 간선은 최대 100개임이 보장됩니다. 또한 중복 간선이나 자기 자신을 향하는 간선은 없음이 보장됩니다.

한 줄에 정수 $f$와 $c$를 공백으로 구분하여 출력합니다. $f$는 그래프의 최대 유량이고, $c$는 최대 유량에 대응하는 최소 비용입니다. 비용이 음수가 될 수 있으니 유의하세요.