本文共 1171 字，大约阅读时间需要 3 分钟。

最小边覆盖问题可以通过将有向无环图（DAG）转化为二分图来解决。具体步骤如下：

以下是详细的解决步骤：

• 转换DAG为二分图：将DAG的顶点分为两部分，构建边连接对应的虚点。
• 寻找最大二分匹配：使用DFS算法计算最大匹配数目。
• 计算最小边覆盖数目：用顶点总数减去最大匹配数目，得到最小边覆盖数目。

通过以上方法，可以高效地解决问题。以下代码实现了这一思路：

#include 
   
    
#include 
    
     
int g[125][125], vis[125], who[125];
int n;
bool find(int x) {
    for(int i = 1; i <= n; ++i) {
        if(g[x][i] && !vis[i]) {
            vis[i] = 1;
            if(!who[i] || find(who[i])) {
                who[i] = x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        memset(g, 0, sizeof(g));
        memset(who, 0, sizeof(who));
        int m, u, v;
        scanf("%d", &n);
        scanf("%d", &m);
        while(m--) {
            scanf("%d %d", &u, &v);
            g[u][v] = 1;
        }
        int sum = 0;
        for(int i = 1; i <= n; ++i) {
            memset(vis, 0, sizeof(vis));
            if(find(i)) sum++;
        }
        printf("%d\n", n - sum);
    }
    return 0;
}
    
   

通过上述代码，可以计算出DAG的最小边覆盖数目，解决问题。

转载地址：http://hljyz.baihongyu.com/