poj 1422 Air Raid(最小路径覆盖—>最大匹配)

 

此题修改过，今天做了2594（Treasure Exploration），写解题报告时发现一个很严重的问题，被我昨天忽略了，首先是搞不清最小边覆盖跟最小路径覆盖，后来是里面的二分匹配求法。

解题思路

题意：

    一个镇里所有的路都是单向路且不会组成回路。

       派一些伞兵去那个镇里，要到达所有的路口，有一些或者没有伞兵可以不去那些路口，只要其他人能完成这个任务。每个在一个路口着陆了的伞兵可以沿着街去到其他路口。我们的任务是求出去执行任务的伞兵最少可以是多少个。

 

思路：

    这个题就是个最小路径覆盖问题。

路径覆盖的定义是：在有向图中找一些路径，使之覆盖了图中的所有顶点，就是任意一个顶点都跟那些路径中的某一条相关联，且任何一个顶点有且只有一条路径与之关联，一个单独的顶点是一条路径.最小路径覆盖就是最少的路径覆盖数。

 如上图，最小路径覆盖的那条路应该是{e1,e4,e5,e6,e7},最小路径覆盖就是1。

 

    有定理： 最小路径覆盖 = 图的顶点数 – 最大匹配数。

 

    其实那个最大匹配数并 非原图的最大匹配数，而是最小路径覆盖的边的条数，是把图中每个点拆成两个点，再算出来的最大匹配数。很容易证明两者是相同的。

 

     可是有一点不明白，为什么原图用匈牙利算法算出最大匹配数，与图的顶点数想减，最后求出的最小路径覆盖是对的呢，而不需要用拆点后的图来算呢？

 

-----原来我建的邻接表它本身就拆点了，所以不矛盾。

源程序

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 125
int g[N][N], used[N], mat[N];
int noi, match;

int find(int k)
{
    int i, j;
    for(i=1; i<= g[k][0]; i++)
    {
        j = g[k][i];
        if(!used[j])
        {
            used[j] = 1;
            if(!mat[j] || find(mat[j]))
            {
                mat[j] = k;
                return 1;
            }
        }
    }
    return 0;
}

void hungary()
{
    int i;
    for(i=1; i<= noi; i++)
    {
        match += find(i);
        memset(used, 0, sizeof(used));
    }
}

int main()
{
    int i, j;
    int t, nos, start, end;
    freopen("in.txt", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &noi, &nos);
        memset(g, 0, sizeof(g));
        memset(mat, 0, sizeof(mat));
        for(i=1; i<=nos; i++)
        {
            scanf("%d%d", &start, &end);
            g[start][++g[start][0]] = end;
        }
        match = 0;
        hungary();
        printf("%d\n", noi-match);
    }
    getch();
    return 0;
}

Problem:		User:
Memory: 220K		Time: 0MS
Language: C++		Result: Accepted