W3CHINA.ORG讨论区--请教解"maximum cardinality with maximum weight in bipartite graph"的算法？

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

是否可以转化成最小费用最大流来做？

有更好的办法吗？

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

能具体叙述一下问题吗？

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

最小费用最大流的方法已经是最优的了

采用连续最短路算法 + 线性规划对偶性优化的原始对偶算法和最大权匹配的KM算法都是O(n3)

而且最小费用最大流又较KM好写 ... 所以推荐最小费用最大流 ...

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

最优匹配问题，采用KM算法，复杂度O(n^3)
效果远胜最小费用最大流，而且很好写。

/*
  Hungary 算法求二部图的最优匹配
  输入：C  -- 二部图的利润矩阵，C[x][y] >=0 表示x和y匹配的利润，
             若x和y之间没有边则C[x][y]=0
       nx -- 二部图的节点集合X中的元素数目
       ny -- 二部图的节点集合Y中的元素数目
  输出：X, Y -- 最优匹配中X,Y集合中节点所匹配的节点的id，-1表示该节点没有被匹配
               注意，若C[i][X[i]] = 0，则最终的结果中可以删除这一匹配，因为
        有无这一匹配对最大利润没有影响
  复杂度：
  注意：输入必须保证 C[x][y] >= 0
*/
void optmatch(Graph C, int nx, int ny, Path X, Path Y)
{
    Path Lx, Ly, Q, prev;
    int i, j, k, s, head, tail;

// 要保证Y中的节点数目比X中的多，从而使X中的所有节点都可以被匹配
if (ny < nx) ny = nx;

    for (i = 0; i < nx; i++) {
Lx[i] = Ly[i] = 0;
for (j = 0; j < ny; j++) {
     Lx[i] = max(Lx[i], C[i][j]);
}
    }
    memset(X, -1, sizeof(Path));
    memset(Y, -1, sizeof(Path));
    i = 0;
    while (i < nx) {
memset(prev, -1, sizeof(Path));
for (Q[0] = i, head = 0, tail = 1; head < tail && X[i] < 0; head++) {
     s = Q[head];
     for (j = 0; j < ny && X[i] < 0; j++) {
  if (Lx[s] + Ly[j] > C[s][j] || prev[j] >= 0) continue;
  Q[tail++]  = Y[j];
  prev[j] = s;
  if (Y[j] < 0) {
      while (j >= 0) {
   s = prev[j];
   Y[j] = s;
   k = X[s];
   X[s] = j;
   j = k;
      }
  }
     }
}
if (X[i] >= 0) {
     i++;
} else {
     k = INT_MAX;
     for (head = 0; head < tail; head++) {
  s = Q[head];
  for (j = 0; j < ny; j++) {
      if (prev[j] == -1) {
   k = min(k, Lx[s] + Ly[j] - C[s][j]);
      }
  }
     }
     for (j = 0; j < tail; j++) {
  Lx[Q[j]] -= k;
     }
     for (j = 0; j < ny; j++) {
  if (prev[j] >= 0) Ly[j] += k;
     }
}
    }
}

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我记得KM算法是很容易写成N^4的 , 但是效果却和N^3差不多 , 所以一直用有保证的费用流 ...

但是费用流也十分好写吧 .

冒昧一下 , 你这个我怎么看都有点像N^4的 ... 不过我不用C 可能看错了 ...

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我很负责的告诉你我这个是O(n^3)的

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

啊 ... 或许我真是看错了 ... 还是继续写mincostflow算了 ...

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

请教一下
什么是连续最短路算法 + 线性规划对偶性优化的原始对偶算法
最近刚开始看有关最大流算法的文章
有个问题始终搞不懂
原始对偶算法是如何与迭代算法结合起来的？
迭代的限制条件又是如何列出的？
哪位好心人指点一下啊


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	125.000ms