【线性规划与网络流24题 3】最小路径覆盖

Description

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

提示：设V={1，2，... ，n}，构造网络 G1=(V1,E1)如下：
V1 = { x0, x1, ..., xn} U { y0, y1, ..., yn} ,
E1 = {(x0,xi):i包含于V} U {(yi,y0):i包含于V} U {(xi,yj):(i,j)包含于E}
每条边的容量均为1。求网络G1 的（x0,y0 ）最大流。

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

Input

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

Output

/*
程序运行结束时，将最小路径覆盖输出。
从第 1 行开始，每行输出一条路径。
文件的最后一行是最少路径数
按字典序输出路径。
*/
一行，包含一个整数，表示最少路径数

Sample Input

Sample Output

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

要求的是最少的路径条数

在点数一定的情况之下，要是希望路径条数越少，那么匹配数肯定越多

所以：我们需要建图跑出最大流

构造二分图，把原图每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图中存在的每条边(i,j)，在二分图中连接边(Xi,Yj)。
然后把二分图最大匹配模型转化为网络流模型，求网络最大流

最小路径覆盖的条数，就是原图顶点数，减去二分图最大匹配数

如何求匹配方案呢？

还是一样的：dfs！

因为每条边要么能走，要么不能走，其边上的flow值是固定的（因为容量为1）

根据dfs一条路走到黑，就是某一条路径

用vis数组标记一下，让每个点都访问一次即可

//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;

const int maxn=1100;
const int maxm=1200010;
const int INF=999999;

int s,t,tot,n,m;
struct Edge{
	int to,nxt,cap,flow;
}edge[maxm];
int tol,Head[maxn];
bool flag[maxn];
int path[maxn],num;

void init(){
	memset(Head,-1,sizeof(Head));
	tol=2;
}

void addedge(int u,int v,int w,int rw=0){
	edge[tol].to=v;
	edge[tol].cap=w;
	edge[tol].flow=0;
	edge[tol].nxt=Head[u];
	Head[u]=tol++;
	
	edge[tol].to=u;
	edge[tol].cap=rw;
	edge[tol].flow=0;
	edge[tol].nxt=Head[v];
	Head[v]=tol++;
}

int Q[maxn],dep[maxn],cur[maxn],sta[maxn];

bool bfs(int s,int t,int n){
	int front=0,tail=0;
	memset(dep,-1,sizeof(dep[0])*(n+1));
	dep[s]=0;
	Q[tail++]=s;
	while(front<tail){
		int u=Q[front++];
		for(int i=Head[u];i!=-1;i=edge[i].nxt){
			int v=edge[i].to;
			if (edge[i].cap>edge[i].flow&&dep[v]==-1){
				dep[v]=dep[u]+1;
				if (v==t) return true;
				Q[tail++]=v;
			}
		}
	}
	return false;
}

int dinic(int s,int t,int n){
	int maxflow=0;
	while(bfs(s,t,n)){
		for(int i=0;i<n;i++) cur[i]=Head[i];
		int u=s,tail=0;
		while(cur[s]!=-1){
			if (u==t){
				int tp=INF;
				for(int i=tail-1;i>=0;i--) 
					tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
				maxflow+=tp;
				for(int i=tail-1;i>=0;i--){
					edge[sta[i]].flow+=tp;
					edge[sta[i]^1].flow-=tp;
					if (edge[sta[i]].cap-edge[sta[i]].flow==0) tail=i;
				}
				u=edge[sta[tail]^1].to;
			}
			else if (cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
				sta[tail++]=cur[u];
				u=edge[cur[u]].to;
			}
			else{
				while(u!=s&&cur[u]==-1) u=edge[sta[--tail]^1].to;
				cur[u]=edge[cur[u]].nxt;
			}
		}
	}
	return maxflow;
}

void getpath(int u){  
    if (u>2*n) return;
    flag[u]=1;
    num++;
    path[num]=u;
    for(int i=Head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if (!flag[v]&&v&&edge[i].flow)
        	getpath(v-n);
    }  
}  

int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//freopen("path3.in","r",stdin);
	//freopen("path3.out","w",stdout);
	init();
	int u,v;
	scanf("%d%d",&n,&m);
	s=0;
	t=n+n+1;
	tot=n+n+2;
	while(m--){
		scanf("%d%d",&u,&v);
		//maze[u][v+n]=1;
		addedge(u,v+n,1);
	}
	for(int i=1;i<=n;i++){
		//maze[s][i]=1;
		addedge(s,i,1);
		//maze[i+n][t]=1;
		addedge(i+n,t,1);
	}
	int maxflow=dinic(s,t,tot);
	/*
	memset(flag,false,sizeof(flag));
	for(int i=1;i<=n;i++)
		if (!flag[i]){
			num=0;
			getpath(i);
			for(int j=1;j<=num;j++)
				printf("%d%c",path[j],j==num?'\n':' ');
		}
	*/
	printf("%d\n",n-maxflow);
	return 0;
}