给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个 顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶 点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少 的路径覆盖。 设计一个有效算法求一个有向无环图G 的最小路径覆盖。 提示：设V={1，2，... ，n}，构造网络G1=(V1,E1)如下：
每条边的容量均为1。求网络G1的（ x0 , y0 ）最大流。 编程任务： 对于给定的有向无环图G，编程找出G的一个最小路径覆盖。
看了题面，很多人还是不懂题意，什么是最小路径覆盖这是个问题。一共有N个点，M条有向边，我们想用其中的一串可以合并起来的有向边，譬如这样"1->2; 2->3; 3->4"合并一下，就是"1->4"并且把链上的所有的点都给遍历到了（1，2，3，4点都路过了）。我们要求的就是最少用几条边，可以把所有的点都给覆盖了。
关于怎么建边呢，我们这么想，对于每条边，一开始我们一共有M条边，有N个点，我们每次把两条边合并的时候就会去减少一条最小路径覆盖，所以我们要求的就是最多可以合并多少条边。那么怎么合并边，是不是可以将边推到点的关系上去，因为每个点最多被经过一次，也就是被访问过一次。那么，我们是不是将点的关系表示出来就可以了？
那么，在以有向无环图为基础的时候，我们把每个点拆开来，表示的是出发、达到的关系：点i拆成{ i, i' }，那么，建立对全体的点：S->i 以及 i'->T，其余的点，如果有"u->v"这样的关系的时候，就建立" u->v' "这样的点，表示的是从u出发可以达到v，如果我们需要把这两个点缩成一个点的话，那么就可以减少一条边的需要，我们跑最大流，就是为了得到最多可以减少多少条边。
建边：
S -> i
i' -> T
u -> v'
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r namespace fastIO { #define BUF_SIZE 100000 //fread -> read bool IOerror = 0; inline char nc() { static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE; if(p1 == pend) { p1 = buf; pend = buf + fread(buf, 1, BUF_SIZE, stdin); if(pend == p1) { IOerror = 1; return -1; } } return *p1++; } inline bool blank(char ch) { return ch == ' ' || ch == 'n' || ch == 'r' || ch == 't'; } inline void read(int &x) { char ch; while(blank(ch = nc())); if(IOerror) return; for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0'); } #undef BUF_SIZE }; using namespace fastIO; using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxN = 307, maxE = 1.5e4 + 7, S = 0; int N, M, head[maxN], cur[maxN], cnt, T, top[maxN], tot, indu[maxN]; struct Eddge { int nex, to, flow; Eddge(int a=-1, int b=0, int c=0):nex(a), to(b), flow(c) {} }edge[maxE], path[maxN]; inline void addEddge(int u, int v, int flow) { edge[cnt] = Eddge(head[u], v, flow); head[u] = cnt++; } inline void _add(int u, int v, int flow) { addEddge(u, v, flow); addEddge(v, u, 0); } int deep[maxN]; queue<int> Q; bool bfs() { memset(deep, 0, sizeof(deep)); deep[S] = 1; while(!Q.empty()) Q.pop(); Q.push(S); while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i=head[u], v, f; ~i; i=edge[i].nex) { v = edge[i].to; f = edge[i].flow; if(f && !deep[v]) { deep[v] = deep[u] + 1; Q.push(v); } } } return deep[T]; } int dfs(int u, int dist) { if(u == T) return dist; for(int &i = cur[u], v, f; ~i; i=edge[i].nex) { v = edge[i].to; f = edge[i].flow; if(f && deep[v] == deep[u] + 1) { int di = dfs(v, min(f, dist)); if(di) { edge[i].flow -= di; edge[i^1].flow += di; return di; } } } return 0; } int Dinic() { int ans = 0, tmp; while(bfs()) { for(int i=S; i<=T; i++) cur[i] = head[i]; while((tmp = dfs(S, INF))) ans += tmp; } return ans; } inline void addPath(int u, int v) { path[tot] = Eddge(top[u], v); top[u] = tot++; } inline void serch(int u) { printf("%d ", u); for(int i=top[u], v; ~i; i=path[i].nex) { v = path[i].to; serch(v); } } inline void solve() { for(int u=1; u<=N; u++) { for(int i=head[u], v, f; ~i; i=edge[i].nex) { v = edge[i].to; f = edge[i^1].flow; if(v > N && f) { addPath(u, v - N); indu[v - N]++; } } } for(int i=1; i<=N; i++) if(!indu[i]) { serch(i); printf("n"); } } inline void init() { cnt = tot = 0; T = (N << 1) + 1; for(int i=S; i<=T; i++) head[i] = top[i] = -1; for(int i=1; i<=N; i++) indu[i] = 0; } int main() { //scanf("%d%d", &N, &M); read(N); read(M); init(); for(int i=1, u, v; i<=M; i++) { //scanf("%d%d", &u, &v); read(u); read(v); _add(u, v + N, 1); } for(int i=1; i<=N; i++) { _add(S, i, 1); _add(i + N, T, 1); } int ans = N - Dinic(); solve(); printf("%dn", ans); return 0; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
