本文共 1136 字，大约阅读时间需要 3 分钟。
最小边覆盖问题可以通过将有向无环图（DAG）转化为二分图来解决。具体步骤如下：
转化问题：将DAG的顶点分为两部分，构建二分图，其中原图的每个顶点对应两个虚点，分别属于二分图的两部分。
建立匹配：在二分图中寻找最大匹配。由于原图是DAG，不存在环，因此二分匹配中也不会出现环。
计算覆盖数：最小边覆盖数目等于顶点数减去最大二分匹配数目。
以下是详细的解决步骤：
通过以上方法，可以高效地解决问题。以下代码实现了这一思路：
#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/