【luogu P2764 最小路径覆盖问题】 模板

题目链接：https://www.luogu.org/problemnew/show/P2764

把每个点在左边建一遍右边建一遍，再加上源点汇点，跑最大流，n-最大流就是答案。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <queue>

 #include <cstring>

 using namespace std;

 const int inf = 1e9;

 const int maxn = ;

 int n, m, s, t, deep[maxn], maxflow, pre[maxn], st;

 struct EDG{

     int next, to, flow;

 }edge[maxn];

 int cnt = -, head[maxn], cur[maxn];

 queue<int> q;

 void add(int u, int v, int w)

 {

     edge[++cnt].next = head[u];

     edge[cnt].to = v;

     edge[cnt].flow = w;

     head[u] = cnt;

     edge[++cnt].next = head[v];

     edge[cnt].to = u;

     edge[cnt].flow = ;

     head[v] = cnt;

 }

 bool bfs(int s, int t)

 {

     for(int i = s; i <= t; i++)

     {

         cur[i] = head[i];

         deep[i] = ;

     }

     deep[s] = ;

     queue<int> q;

     q.push(s);

     while(!q.empty())

     {

         int now = q.front(); q.pop();

         for(int i = head[now]; i != -; i = edge[i].next)

         {

             if(!deep[edge[i].to] && edge[i].flow)

             {

                 q.push(edge[i].to);

                 deep[edge[i].to] = deep[now]+;

             }

         }

     }

     if(deep[t]) return true;

     return false;

 }

 int dfs(int now, int t, int limit)

 {

     if(!limit || now == t) return limit;

     int flow = , f;

     for(int i = cur[now]; i != -; i = edge[i].next)

     {

         cur[now] = i;

         if(deep[edge[i].to] == deep[now]+ && (f = dfs(edge[i].to, t, min(limit, edge[i].flow))))

         {

             flow += f;

             limit -= f;

             edge[i].flow -= f;

             edge[i^].flow += f;

             if(!limit) break;

         }

     }

     return flow;

 }

 void Dinic(int s, int t)

 {

     while(bfs(s,t))

     maxflow += dfs(s,t,inf);

 }

 void output(int x)

 {

     printf("%d ",x);

     for(int i = head[x]; i != -; i = edge[i].next)

     {

         if(edge[i].flow ==  && edge[i].to - n >  && edge[i].to - n <= n)

         {

             output(edge[i].to - n);

             break;

         }

     }

     return ;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i = ; i <= *n+; i++)

     head[i] = -;

     s = , t = *n+;

     for(int i = ; i <= m; i++)

     {

         int u, v;

         scanf("%d%d",&u,&v);

         add(u,v+n,);

     }

     for(int i = ; i <= n; i++)

     {

         add(,i,);

         add(i+n,*n+,);

     }

     Dinic(s,t);

     for(int i=head[*n+];i!=-;i=edge[i].next)

     {

         if(edge[i^].flow==)

             pre[++st]=edge[i].to;

     }

     for(int i=;i<=st;i++)

     {

         output(pre[i]-n);

         printf("\n");

     }

     printf("%d",n - maxflow);

     return ;

 }