网络流24题-最小路径覆盖问题

题目链接：https://www.luogu.org/problemnew/show/P2764
有向无环图G的最小路径点覆盖包含的路径数等于n减去拆点二分图G2的最大匹配数
  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 const int inf=0x3f3f3f3f;
  5 const int MAXN=10000;
  6 const int MAXM=100000;
  7 struct Edge
  8 {
  9     int to,nxt,cap,flow;
 10 }edge[MAXM];
 11 int head[MAXN],tot,dis[MAXN],S,T,n,m;
 12 void init()
 13 {
 14     memset(head,-1,sizeof(head));
 15     tot=0;
 16 }
 17 void addedge(int u,int v,int cap)
 18 {
 19     edge[tot].to=v; edge[tot].cap=cap;  edge[tot].flow=0;
 20     edge[tot].nxt=head[u];  head[u]=tot++;
 21 
 22     edge[tot].to=u; edge[tot].cap=0;  edge[tot].flow=0;
 23     edge[tot].nxt=head[v];  head[v]=tot++;
 24 }
 25 queue<int>q;
 26 bool bfs()
 27 {
 28     memset(dis,0,sizeof(dis));
 29     while(!q.empty())   q.pop();
 30     q.push(S);
 31     dis[S]=1;
 32     while(!q.empty())
 33     {
 34         int u=q.front();q.pop();
 35         for(int i=head[u];i!=-1;i=edge[i].nxt)
 36         {
 37             int v=edge[i].to;
 38             if(!dis[v]&&edge[i].cap>edge[i].flow)
 39             {
 40                 dis[v]=dis[u]+1;
 41                 q.push(v);
 42             }
 43         }
 44     }
 45     return dis[T];
 46 }
 47 int dfs(int u,int f)
 48 {
 49     if(u==T)    return f;
 50     for(int i=head[u];i!=-1;i=edge[i].nxt)
 51     {
 52         int v=edge[i].to;
 53         if(dis[u]+1==dis[v]&&edge[i].cap>edge[i].flow)
 54         {
 55             int f1=dfs(v,min(f,edge[i].cap-edge[i].flow));
 56             if(f1)
 57             {
 58                 edge[i].flow+=f1;
 59                 edge[i^1].flow-=f1;
 60                 return f1;
 61             }
 62         }
 63     }
 64     return 0;
 65 }
 66 int dinic()
 67 {
 68     int ans=0;
 69     while(bfs())    ans+=dfs(S,inf);
 70     return ans;
 71 }
 72 int to[MAXN];
 73 bool vis[MAXN];
 74 int main()
 75 {
 76     ios::sync_with_stdio(false);
 77     cin.tie(0); cout.tie(0);
 78     cin>>n>>m;
 79     init();
 80     S=0;
 81     T=2*n+1;
 82     int u,v;
 83     for(int i=1;i<=m;i++)
 84     {
 85         cin>>u>>v;
 86         addedge(u,v+n,1);
 87     }
 88     for(int i=1;i<=n;i++)
 89     {
 90         addedge(S,i,1);
 91         addedge(i+n,T,1);
 92     }
 93     int ans=n-dinic();
 94     for(int i=1;i<=n;i++)
 95     {
 96         for(int j=head[i];j!=-1;j=edge[j].nxt)
 97         {
 98             if(edge[j].flow==1)
 99             {
100                 to[i]=edge[j].to-n;
101                 break;
102             }
103         }
104     }
105     for(int i=1;i<=n;i++)
106     {
107         int flag=0;
108         if(!vis[i])
109         {
110             while(i)
111             {
112                 vis[i]=1;
113                 if(flag)    cout<<" ";
114                 flag=1;
115                 cout<<i;
116                 i=to[i];
117             }
118             cout<<endl;
119         }
120     }
121     cout<<ans<<endl;
122     return 0;
123 }
如有错误，请指正，感谢！