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

2014年2月28日9,4120

Description

问题描述：

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

编程任务：

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

Input Format

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

Output Format

从第1 行开始，每行输出一条路径(行末无空格)。文件的最后一行是最少路径数。

Sample Input

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

Sample Output

1 4 7 10 11
2 5 8
3 6 9
3

1 4 7 10 11

2 5 8

3 6 9

将每个点都分别放入xy集合中

如果u到v有一条边,则x集合的u向y集合的v连一条权值inf的边

S向x集合的点连边，权值1，y集合的点向T连边，权值1，做一遍最大流，得出最大匹配数

ans=n-最大匹配

如果无匹配，显然要n条路径才能覆盖所有点，两个点匹配意味着将可以把它们用一条路径覆盖，路径数就可以减1

#include<cstdio>
#include<cstring>
#include<iostream>
#define inf 0x7fffffff
using namespace std;
int n,m,cnt=1,ans,head[10001],q[10001],to[10001],h[10001];
bool mark[10001];
struct data{int to,next,v;}e[2000001];
void ins(int u,int v,int w)
{cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,0);}
bool bfs()
{
     int t=0,w=1,i,now;
     memset(h,-1,sizeof(h));
     h[0]=q[0]=0;
     while(t<w)
     {
               now=q[t];t++;
               i=head[now];
               while(i)
               {
                       if(h[e[i].to]==-1&&e[i].v){h[e[i].to]=h[now]+1;q[w++]=e[i].to;}
                       i=e[i].next;
                       }
               }
     if(h[8001]==-1)return 0;
     return 1;
 }
int dfs(int x,int f)
{
    if(x==8001)return f;
    int i=head[x];
    int w,used=0;
    while(i)
    {
            if(e[i].v&&h[e[i].to]==h[x]+1)
            {
                w=f-used;
                w=dfs(e[i].to,min(w,e[i].v));
                if(w)
				{
				   to[x]=e[i].to;
                   if(e[i].to-n>0)mark[e[i].to-n]=1;
                }
                e[i].v-=w;
                e[i^1].v+=w;
                used+=w;
                if(used==f)return f;                      
                }
                i=e[i].next;
            }
    if(!used)h[x]=-1;
    return used;
    }
void dinic(){while(bfs())ans-=dfs(0,inf);}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
       {
          int u,v;
          scanf("%d%d",&u,&v);
          insert(u,v+n,inf);
       }
    for(int i=1;i<=n;i++)insert(0,i,1);
	for(int i=1;i<=n;i++)insert(i+n,8001,1);
	ans=n;
	dinic();
    for(int i=1;i<=n;i++)
    {
        if(mark[i])continue;
        printf("%d",i);
        int k=i;
        while(to[k])
        {
            printf(" %d",to[k]-n);
            k=to[k]-n;
        }
        printf("\n");
    }
	printf("%d",ans);
    return 0;   	
}

#include<cstdio>

#include<cstring>

#include<iostream>

#define inf 0x7fffffff

using namespace std;

int n,m,cnt=1,ans,head[10001],q[10001],to[10001],h[10001];

bool mark[10001];

struct data{int to,next,v;}e[2000001];

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

{cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;}

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

{ins(u,v,w);ins(v,u,0);}

bool bfs()

{

int t=0,w=1,i,now;

memset(h,-1,sizeof(h));

h[0]=q[0]=0;

while(t<w)

{

now=q[t];t++;

i=head[now];

while(i)

{

if(h[e[i].to]==-1&&e[i].v){h[e[i].to]=h[now]+1;q[w++]=e[i].to;}

i=e[i].next;

}

if(h[8001]==-1)return 0;

return 1;

}

int dfs(int x,int f)

{

if(x==8001)return f;

int i=head[x];

int w,used=0;

while(i)

{

if(e[i].v&&h[e[i].to]==h[x]+1)

{

w=f-used;

w=dfs(e[i].to,min(w,e[i].v));

if(w)

{

to[x]=e[i].to;

if(e[i].to-n>0)mark[e[i].to-n]=1;

}

e[i].v-=w;

e[i^1].v+=w;

used+=w;

if(used==f)return f;

}

i=e[i].next;

}

if(!used)h[x]=-1;

return used;

}

void dinic(){while(bfs())ans-=dfs(0,inf);}

int main()

{

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

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

{

int u,v;

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

insert(u,v+n,inf);

}

for(int i=1;i<=n;i++)insert(0,i,1);

for(int i=1;i<=n;i++)insert(i+n,8001,1);

ans=n;

dinic();

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

{

if(mark[i])continue;

printf("%d",i);

int k=i;

while(to[k])

{

printf(" %d",to[k]-n);

k=to[k]-n;

}

printf("\n");

}

printf("%d",ans);

return 0;

}

« 「CODEVS1907」方格取数3 「BZOJ1412」[ZJOI2009] 狼和羊的故事 »

hzwer.com _ Home | http://hzwer.com

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

Description

Input Format

Output Format

Sample Input

Sample Output

分类目录

热门文章

Myfriends

近期评论