如题= =自用模板

可用于二分图(树/有向无环图)的最小路径覆盖 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*DAG不可重点的最小路径覆盖*/
import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		FastScanner sc=new FastScanner();
		PrintWriter pw=new PrintWriter(System.out);
		BGraph bg=new BGraph();
		int t=sc.nextInt();
		while(sc.hasNext()){
			int n=sc.nextInt();
			int m=sc.nextInt();
			bg.init();
			for(int i=0;i<m;i++){
				int a=sc.nextInt();
				int b=sc.nextInt();
				bg.add_diredge(a-1, b-1);
				//bg.add_diredge(b-1, a-1);
			}
			int ans=bg.match(n);
			pw.println(ans);
			pw.flush();
		}
	}

}
class BGraph{  
    Edge[]edge;//男女关系  
    boolean[]vis;//m  
    int[]girl;//妹子的归属
    int[]head;
    int cnt;
    int maxn=2005;
    BGraph(){
    	edge=new Edge[maxn*maxn];
    	for(int i=0;i<maxn*maxn;i++){
    		edge[i]=new Edge();
    	}
    	vis=new boolean[maxn];
    	girl=new int[maxn];
    	head=new int[maxn];
    }
    void init(){
    	Arrays.fill(head, -1);
    	cnt=0;
    }
    void add_diredge(int u,int v){
    	edge[cnt].to=v;
    	edge[cnt].next=head[u];
    	head[u]=cnt++;
    }
    boolean find(int u){ //u是男,找妹子   
        for(int i=head[u];i!=-1;i=edge[i].next){
        	int v=edge[i].to;
        	if(!vis[v]){
        		vis[v]=true;
        		if(girl[v]==-1||find(girl[v])){
        			girl[v]=u; //别写反
        			return true;
        		}
        	}
        }
        return false;    
    }   
    int match(int n){ //下标为0~n的男生 返回最大匹配数  DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数
    	int ans=0;
    	Arrays.fill(girl, -1);
    	for(int i=0;i<n;i++){
    		Arrays.fill(vis,false);
    		if(find(i))ans++;
    	}
    	return ans;
    }
}
class Edge{    
    int next;  
    int to;    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*DAG可重点的最小路径覆盖 先跑一边floyd*/
import java.io.*;
import java.util.*;
public class Main {
static int INF=0x3f3f3f3f;
static int[][]maze;
	public static void main(String[] args) {
		FastScanner sc=new FastScanner();
		PrintWriter pw=new PrintWriter(System.out);
		BGraph bg=new BGraph();
		maze=new int[505][505];
		while(sc.hasNext()){
			int n=sc.nextInt();
			int m=sc.nextInt();
			if(n==0&&m==0)break;
			bg.init();	
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(i==j)maze[i][j]=0;
					else maze[i][j]=INF;
				}
			}
			for(int i=0;i<m;i++){
				int a=sc.nextInt();
				int b=sc.nextInt();
				maze[a][b]=1;
			}
			for(int k=1;k<=n;k++){
				for(int i=1;i<=n;i++){
					for(int j=1;j<=n;j++){
						if(maze[i][k]+maze[k][j]<maze[i][j]){
							maze[i][j]=1;
							break;
						}
					}
				}
			}
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(i!=j&&maze[i][j]<INF){
						bg.add_diredge(i, j);
					}
				}
			}
			int ans=bg.match(n);
			pw.println(n-ans);
			pw.flush();
		}
	}

}
class BGraph{  
    Edge[]edge;//男女关系  
    boolean[]vis;//m  
    int[]girl;//妹子的归属
    int[]head;
    int cnt;
    int maxn=2005;
    BGraph(){
    	edge=new Edge[250050];
    	for(int i=0;i<250050;i++){
    		edge[i]=new Edge();
    	}
    	vis=new boolean[maxn];
    	girl=new int[maxn];
    	head=new int[maxn];
    }
    void init(){
    	Arrays.fill(head, -1);
    	cnt=0;
    }
    void add_diredge(int u,int v){
    	edge[cnt].to=v;
    	edge[cnt].next=head[u];
    	head[u]=cnt++;
    }
    boolean find(int u){ //u是男,找妹子   
        for(int i=head[u];i!=-1;i=edge[i].next){
        	int v=edge[i].to;
        	if(!vis[v]){
        		vis[v]=true;
        		if(girl[v]==-1||find(girl[v])){
        			girl[v]=u; //别写反
        			return true;
        		}
        	}
        }
        return false;    
    }   
    int match(int n){ //下标为0~n的男生 返回最大匹配数  DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数
    	int ans=0;
    	Arrays.fill(girl, -1);
    	for(int i=1;i<=n;i++){
    		Arrays.fill(vis,false);
    		if(find(i))ans++;
    	}
    	return ans;
    }
}
class Edge{    
    int next;  
    int to;    
}