HDU 4370 0 or 1 题解(最短路+条件转化)

题目大意

题目描述:给定一个 n * n 的矩阵 C,现在请你求一个01矩阵X满足以下三个条件:

  1. \(X[1][2]+X[1][3]+…+X[1][n]=1\)
  2. \(X[1][n]+X[2][n]+…+X[n-1][n]=1\)
  3. \(对于 1 < i < n, Sum(X[k][i])(1 <= k <= n) = Sum(X[i][j])(1 <= j <= n)\)
    同时最小化化 \(sum(X[i][j] * C[i][j]) (1 <= i,j <= n) n <= 300\)

题目思路

其实就是要转化思维

第一个条件理解为1的出度为1

第二个条件理解为n的入度为1

第三个条件理解为其他点的出度等于入度

那么题目就是求\(1\)到\(n\)的最短路

还有一种情况就是包括\(1\)的环长度+包括\(n\)的环的长度

两者取最小值即可

上一篇:HDU 6166 Senior Pan 题解(二进制分组+最短路)


下一篇:1011 A+B 和 C (15 分)