Posted on 2007-04-16 13:27
oyjpart 阅读(2629)
评论(7) 编辑 收藏 引用 所属分类:
ACM/ICPC或其他比赛
遇到下面一个题目
给出一个有向图的各个点的in-degree和out-degree的时候 怎样求得这个图的边的情况？
答案是：
1.把所有的in-degree和所有的out-degree相加，如果不相等 则此图无法建成 输出impossible
2.如果可能建 立即得出边应该为 M = sum(in-degree) 因为每条边必然导致 indegree+1
3.对这个M条边做分配 如何分配呢？ 如下方案可满足要求：
最大流算法
1.将每个点化成入点和出点（1分为2）
由于对于有向图中的边是从A的出点到B的入点 所以应该如下建图：
2.引出source从所有有向图中的点的出点的边 权为out-degree
3.引出所有有向图中的点的入点的边到sink的边 权为 in-degree
4.引出所有有向图任一点到另一点的边 权统一为1（在没有重边的题目要求下）
5.执行最大流算法 如果得到 M 的最大流 则满足题意 输出所有这些边
(如是从B点的出点到A的入点 则输出B->A)