题目描述

1.二分图、不存在奇数环、染色法不存在矛盾
2.匈牙利算法，匹配、最大匹配、匹配点、增广路径
3.最小点覆盖、最大独立集、最小路径点覆盖(最小路径重复点覆盖)
最大匹配数=最小点覆盖=总点数-最大独立集=总点数-最小路径点覆盖

最小路径点覆盖：用最少的互不相交的路径，把所有点覆盖

一边的总点数n-m 为答案

邻接表的传递闭包dfs求法，需要开一个reach数组，reach[i][j]==1表示i可以到j，然后用dfs更新

具体做法如下：

void dfs(int u,int v)
{
    reach[u][v]=1;
    for(int i=h[v];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!reach[u][j])
        {
            dfs(u,j);
        }
    }
}
for(int i=1;i<=n;i++)
    {
        dfs(i,i);
    }
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=n;j++)
    {
        if(i!=j && reach[i][j])
        {
            add(i,j);
        }
    }
}

#include <iostream>
#include <cstring>

using namespace std;

const int N=210,M=60010;
int h[N],e[M],ne[M],idx,st[N],match[N];
int n,m;
int reach[N][N];


void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

//求传递闭包，a->b,b->c,a应该也能到c
void dfs(int u,int v)
{
    reach[u][v]=1;
    for(int i=h[v];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!reach[u][j])
        {
            dfs(u,j);
        }
    }
}

int find(int x)
{
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=1;
            if(!match[j]||find(match[j]))
            {
                match[j]=x;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof st);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        dfs(i,i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j && reach[i][j])
            {
                add(i,j);
            }
        }
    }

    int res=0;
    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof st);
        if(find(i)) res++;
    }
    cout<<n-res;
    return 0;
}

二刷，在求传递闭包时做了优化，用拓扑排序优化了每个点，这样只需要遍历每个入度为0的点，reach[i]代表这个点可达，而不是代表从i->j可达

每次在dfs里对状态s更新，状态s[i]是一个迭代，代表i可达的所有状态，如果可达j，则可达j所可达的所有点。

#include <iostream>
#include <cstring>
#include <bitset>
using namespace std;

const int N=210,M=60010;
int h[N],e[M],ne[M],idx,st[N],match[N];
int n,m;
int reach[N];
int d[N];
bitset<N> s[N];

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

//求传递闭包，a->b,b->c,a应该也能到c
void dfs(int u)
{
    reach[u]=1;
    s[u][u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!reach[j])
        {
            dfs(j);
        }
        s[u]|=s[j];
    }
}

int find(int x)
{
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=1;
            if(!match[j]||find(match[j]))
            {
                match[j]=x;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof st);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(d[i]==0)
        {
           dfs(i); 
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j && s[i][j])
            {
                add(i,j);
            }
        }
    }

    int res=0;
    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof st);
        if(find(i)) res++;
    }
    cout<<n-res;
    return 0;
}

三刷，在复习完前面之后比较顺利的ac了

本质还是求最大独立集 = 总点数-最小点覆盖 = 总点数-最大匹配数

本题把传递闭包与最大匹配数融合起来，先要求所有点的传递闭包
这里使用floyd求传递闭包，好像比直接dfs慢了不少

#include <iostream>
#include <cstring>

using namespace std;

const int N=400,M=100100;
int g[N][N];
int st[N];
int match[N];
int n,m;


void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                g[i][j]|=(g[i][k] & g[k][j]);
            }
        }
    }
}

int find(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(g[u][i] && !st[i])
        {
            st[i]=1;
            if(!match[i] || find(match[i]))
            {
                match[i]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    cin>>n>>m;
    //memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=1;
    }
    floyd();

    int res=0;
    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof st);
        if(find(i)) res++;
    }
    cout<<n-res;
    return 0;
}