P2764 最小路径覆盖问题

题目描述

«问题描述：

给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图G 的最小路径覆盖。提示：设V={1，2，.... ，n}，构造网络G1=(V1,E1)如下：

每条边的容量均为1。求网络G1的（ 0 x , 0 y ）最大流。

«编程任务：

对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。

输入输出格式

输入格式：

件第1 行有2个正整数n和m。n是给定有向无环图G 的顶点数，m是G 的边数。接下来的m行，每行有2 个正整数i和j，表示一条有向边(i,j)。

输出格式：

从第1 行开始，每行输出一条路径。文件的最后一行是最少路径数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

1 4 7 10 11

2 5 8

3 6 9

3

这题是一个网络流常用模型，
最小路径覆盖问题；
这题反向思考，就是点的数目-最大的二分匹配；
就是最少的路径数目；
这题算出最小路径，直接套网络流模板就行了；
但是要输出路径这就很恶心了；
我放弃了我自己原来的网络流模板；
找了一个更加适合输出路径的代码；
输出路径真心恶心

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define inf 0x3fffffff

 using namespace std;

 const int maxn = 1e5 + ;

 int head[maxn], sign, cur[maxn];

 int s, t, d[maxn];

 struct node {

     int to, w, next;

 } edge[maxn] ;

 void creat() {

     memset(head, -, sizeof(head));

     sign = ;

 }

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

     edge[sign].to = v;

     edge[sign].w = w;

     edge[sign].next = head[u];

     head[u] = sign++;

     edge[sign].to = u;

     edge[sign].w = ;

     edge[sign].next = head[v];

     head[v] = sign++;

 }

 int bfs() {

     queue<int>q;

     memset(d, , sizeof(d));

     d[s] = ;

     q.push(s);

     while(!q.empty()) {

         int top = q.front();

         q.pop();

         for (int i = head[top] ; ~i  ; i = edge[i].next ) {

             int to = edge[i].to;

             if (edge[i].w >  && d[to] == )  {

                 d[to] = d[top] + ;

                 if (to == t) return ;

                 q.push(to);

             }

         }

     }

     return d[t] != ;

 }

 int dfs(int top, int flow ) {

     if (top == t) return flow;

     int ans = , x = ;

     for (int i = cur[top] ; ~i ; i = edge[i].next)  {

         int to = edge[i].to;

         if (edge[i].w >  && d[to] == d[top] + ) {

             x = dfs(to, min(flow - ans, edge[i].w)) ;

             edge[i].w -= x;

             edge[i ^ ].w += x;

             if (edge[i].w) cur[top] = i;

             ans += x;

             if (ans == flow) return flow;

         }

     }

     if (ans == ) return d[top] = ;

     return ans;

 }

 int dinic(int n) {

     int ans = ;

     while(bfs()) {

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

             cur[i] = head[i];

         ans += dfs(s, inf);

     }

     return ans;

 }

 int n, m, vis[maxn];

 void go(int x, int &f) {

     int loc = x + n;

     vis[x] = ;

     for (int i = head[loc] ; ~i ; i = edge[i].next)

         if (edge[i].w ==   && edge[i].to != n *  + ) go(edge[i].to, f) ;

     if (f == ) f = ;

     printf(" ");

     printf("%d", x);

 }

 int main() {

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

     creat();

     s = , t =  * n + ;

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

         add(s, i, ), add(i + n, t, );

     int x, y;

     while(m--) {

         scanf("%d%d", &x, &y);

         add(x, y + n, );

     }

     int ans = n - dinic(t);

     for (int i = head[t]; ~i ; i = edge[i].next) {

         if (edge[i].w ==  && !vis[edge[i].to - n]) {

             int f = ;

             go(edge[i].to - n, f);

             printf("\n");

         }

     }

     printf("%d\n", ans);

     return ;

 }

巴特西

P2764 最小路径覆盖问题

题目描述

输入输出格式

输入输出样例

最新文章

热门文章