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

题意：

最小路径覆盖，emmm好像跟最少边覆盖差不多。但这俩确实不是一个东西。

最小边覆盖：边数最小的边覆盖集称为最小边覆盖，通俗地讲，就是极小边覆盖中的最小的一个集合。

最小边覆盖在二分图中的应用：最小边覆盖 = 最大独立集 = n - 最大匹配，这个是二分图上的一个性质。

两个很小的点：必须要求原图为二分图；边覆盖集中可能有多条边覆盖同一个顶点，其实可以这条边说是为了覆盖另一个顶点而存在的。

继续说最小路径问题：

为什么是N-ans呢？

再说如何把方案输出？

我们可以用网络流来跑这个二分图，我们知道跑完网络流的图是会被改变的容量不变，流量会变。假设我们发现某条边的容量==流量并且容量不为0，则代表这条边有流量经过，那么我们则可以把这个u，v这两个点做一下标记。用两个数组pre，lst ，pre代表这个点之前是有哪个点流过来的，lst代表这个点之后会流向哪个点。

最后遍历N个点，如果遇到某点的pre==0（意味着这个点是某条简单路径的起点），那么就顺着这个点输出这个简单路径即可。

代码：

#include
   
    using namespace std;const int maxn = 1010;const int maxm = 1e6+10;struct edge{
       long long to, next, cap, flow;  // 容量 和 流量}e[maxm << 1]; int head[maxn], tot;int n, m, s, t, d[maxn], cur[maxn]; // d[]分层，cur[]弧优化inline void addedge(int u, int v, int w) {
       e[++tot] = {
   v, head[u], w, 0}, head[u] = tot;    e[++tot] = {
   u, head[v], 0, 0}, head[v] = tot;}inline bool bfs() {
    // 分层 t-s路径优化    memset(d, 0x3f, sizeof d);    queue
    
      q; q.push(t);    d[t] = 0;    while(!q.empty()) {
           int x = q.front(); q.pop();        for(int i = head[x]; ~i; i = e[i].next) {
               int j = e[i].to;            if (d[j] == d[0] && e[i^1].cap > e[i^1].flow) {
                   d[j] = d[x] + 1;                if (j == s) return true;                q.push(j);            }        }    }    return false;}long long dfs(int x, long long flow, long long used = 0) {
   //used多路增广    if (x == t) return flow;    //for(int i = cur[x]; ~i && flow != used; i = e[ cur[x] = i ].next) {  // 当前弧优化    for(int i = head[x]; ~i && flow != used; i = e[i].next) {
           long long j = e[i].to, f;        if (d[x] - 1 == d[j] && e[i].cap > e[i].flow) {
               f = dfs(j, min(e[i].cap-e[i].flow, flow-used));            if (f) e[i].flow += f, e[i^1].flow -= f, used += f;        }    }    if (!used) d[x] = 0;   // 剪枝优化    return used;}int dinic(){
       long long maxflow = 0;    while(bfs()) {
      // 每次dfs分层都能找到多条增广路        //memcpy(cur, head, sizeof head);        maxflow += dfs(s, INT_MAX);    }    return n-maxflow;}void init(){
       memset(head,-1,sizeof head);    tot=-1;}int pre[maxn],lst[maxn];int main() {
       //freopen("1.in","r",stdin);    init();    cin>>n>>m;    for(int i=0;i
     
      >x>>y;        addedge(x,y+n,1);    }    s=0,t=2*n+2;    for(int i=1;i<=n;i++){
           addedge(s,i,1);        addedge(i+n,t,1);    }    int ans=dinic();    for(int i=1;i<=n;i++){
           for(int j=head[i];~j;j=e[j].next){
               int v=e[j].to;            if(e[j].cap-e[j].flow==0&&e[j].flow==1){
                   pre[v-n]=i;                lst[i]=v-n;            }        }    }    for(int i=1;i<=n;i++){
           if(!pre[i]){
               int u=i;            while(lst[u]!=0){
                   cout<
      <<" ";                u=lst[u];            }            cout<<
     
    
   

转载地址：https://blog.csdn.net/xxxxxiao123/article/details/116614136 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！