#PQJ1644x8350. QOJ 1644_8350

    ID: 2675 传统题 5000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2022 集训强连通分量动态规划

QOJ 1644_8350

标题: ddtt - Problem - QOJ.ac

#8350. ddtt

Statistics

The problem was used in the following contests:

题目描述

d__ 和 d__ 要 t__ t__ 。有一张 n 个点,m 条边的无向图。现在小 q 想要把每条边定向,使得不管 d__ 和 d__ 在哪两个点,d__ 都能顺着这些有向边找到 d__(即强连通)。小 q 想要知道代价最小的方案,注意每条无向边的两种定向方式的代价不同。

输入格式

第一行一个正整数 n 。

接下来 n 行,每行 n 个整数,其中第 i 行第 j 个数代表 ai,j ,表示定向为 i 到 j 的有向边的代价。如果不存在 i,j 之间的边, ai,j=−1 。保证 ai,i=−1 。

输出格式

一行一个整数,表示最小代价。如果无解,输出 −1 。

样例输入 1

4
-1 3 2 -1
3 -1 7 7
5 9 -1 9
-1 6 7 -1

样例输出 1

27

样例输入 2

6
-1 1 2 -1 -1 -1
3 -1 4 -1 -1 -1
5 6 -1 0 -1 -1
-1 -1 0 -1 6 5
-1 -1 -1 4 -1 3
-1 -1 -1 2 1 -1

样例输出 2

-1

数据范围

保证 n≤18 。

subtask1(30pts):保证 n≤7 。

subtask2(30pts):保证 n≤12 。

subtask3(20pts):保证 n≤16 。

subtask4(20pts):无特殊限制。