ssl 2603 网络流24题3 最小路径覆盖问题
问题描述：
给定有向图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 ）最大流。
?编程任务：
【ssl 2603 网络流24题3 最小路径覆盖问题】对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。
输入输出格式
输入格式：
件第1 行有2个正整数n和m。n是给定有向无环图G 的顶点数，m是G 的边数。接下来的m行，每行有2 个正整数i和j，表示一条有向边(i,j)。
输出格式：
从第1 行开始，每行输出一条路径。文件的最后一行是最少路径数。
输入输出样例
输入样例#1：
11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11
输出样例#1：
1 4 7 10 11
2 5 8
3 6 9
3
大意：
求一个图的最小点路径覆盖问题，要输出覆盖路径。
分析：
建立一个新图，将G中的每个点i在新图中拆成两个点i、i’，若G中存在边 << i, j>则在新图中连边 << i, j’ >> ，显然新图是一个二分图，求其最大匹配，则(N-新图最大匹配的值)就是最小点路径覆盖值。
输出路径从每个点开始，遍历一下，因为会跑到i的对点j’，因此下次应该从j开始搜索，如果一边的权为0，则有东西流过，就是解。
代码：
const
maxn=2003;
maxm=200003;
type
node=record
y,c,next,op:longint;
end;
var
e,n,m,s,t,ans,d,x,y,i,j,num:longint;
ls,dis,q,cur,path,v:array [0..maxn] of longint;
g:array [0..maxm*2] of node;
procedure add(u,v,c:longint);
begin
inc(e);
g[e].y:=v;
g[e].c:=c;
g[e].op:=e+1;
g[e].next:=ls[u];
ls[u]:=e;
inc(e);
g[e].y:=u;
g[e].c:=0;
g[e].op:=e-1;
g[e].next:=ls[v];
ls[v]:=e;
end;
function bfs:boolean;
var i,head,tail,tt,u:longint;
begin
for i:=s to t do
dis[i]:=0;
dis[s]:=1;
head:=0;
tail:=1;
inc(tail);
q[tail]:=s;
while head<=tail do
begin
inc(head);
u:=q[head];
i:=ls[u];
while i>0 do
begin
if (g[i].c<>0) and (dis[g[i].y]=0) then
begin
dis[g[i].y]:=dis[u]+1;
if g[i].y=t then exit(true);
inc(tail);
q[tail]:=g[i].y;
end;
i:=g[i].next;
end;
end;
exit(false);
end;
function min(x,y:longint):longint;
begin
if x0 do
begin
if (g[i].c<>0) and (dis[g[i].y]=dis[x]+1) then
begin
f:=dfs(g[i].y,min(g[i].c,maxf));
dec(g[i].c,f);
inc(g[g[i].op].c,f);
ret:=ret+f;
if ret=maxf then break;
end;
i:=g[i].next;
end;
exit(ret);
end;
procedure dinic;
var i:longint;
begin
while bfs do
begin
for i:=s to t do
cur[i]:=ls[i];
ans:=ans+dfs(s,maxlongint);
end;
end;
procedure find(x:longint);
var i,y:longint;
begin
if (x>2*n) or (x<0) then exit;
v[x]:=1;
inc(num);
path[num]:=x;
i:=ls[x];
while i>0 do
begin
y:=g[i].y;
if (v[y]=0) and (y>0) and (g[i].c=0) then
find(y-n);
i:=g[i].next;
end;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
add(x,y+n,1);
end;
for i:=1 to n do
add(0,i,1);
for i:=n+1 to 2*n do
add(i,2*n+1,1);
s:=0;
t:=2*n+1;
fillchar(v,sizeof(v),0);
dinic;
for i:=1 to n do
begin
num:=0;
if v[i]=1 then continue;
fillchar(path,sizeof(path),0);
find(i);
for j:=1 to num do
write(path[j],' ');
writeln;
end;
writeln(n-ans);
end. 推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- 猎杀IP
- 自媒体形势分析
- 数学大作战
- 2018.03.18
- 星期天的下午茶（一）
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的（传统文化与身心健康）教育体系心得体会
- 三国谋略22（找准你的定位）
- 何以燃夏
- LSTM网络层详解及其应用实例