By

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1143

Solution

题意可以转化为有向无环图求最小可相交路径覆盖。用二分图做
最小可享交路径覆盖=Floyd求出连通性后的最小不相交路径覆盖。
而最小不相交路径覆盖=原图节点数-最大匹配。
证明：
开始每个点独立一条路径，共有n条不相交路径，每次在二分图中加一条边相当于将两条路径合并成一条路径，因为加的边不会有公共点（匹配的定义），所以路径中不会有公共点出现，所以：最小不相交路径覆盖=原图节点数-最大匹配。

Code 

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 105
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}
struct edge{
    ll to,next;
}e[N*N*2];
ll head[N],flag[N],link[N],f[N][N];
ll n,m,tot,ans;
void add(ll u,ll v){
    e[++tot]=(edge){v,head[u]}; head[u]=tot;
}
bool find(ll u){
    for (ll i=head[u],v=e[i].to;i;i=e[i].next,v=e[i].to)
        if (!flag[v]){
            flag[v]=1;
            if (!link[v]||find(link[v])){
                link[v]=u; return 1;
            }
        }
    return 0;
}
int main(){
    n=read(); m=read();
    for (ll i=1;i<=m;i++){
        ll u=read(),v=read();
        f[u][v]=1;
    }
    for (ll k=1;k<=n;k++)
    for (ll i=1;i<=n;i++)
    for (ll j=1;j<=n;j++)
        f[i][j]|=f[i][k]&f[k][j];
    for (ll i=1;i<=n;i++)
    for (ll j=1;j<=n;j++)
        if (f[i][j]&&i!=j) add(i,j);
    ans=n;
    for (ll i=1;i<=n;i++){
        memset(flag,0,sizeof flag);
        if (find(i)) ans--;
    }
    printf("%d",ans);
}
文章目录
  1. 1. Solution
  2. 2. Code