二分图

二分图判定:

题目链接:二分图判定

dfs:

const int __=10005;

bool flag;
int col[__];
vector<int>G[__];

void dfs(int x,int y)
{
    if(col[x])
    {
        if(col[x]!=y)flag=false;
        return;
    }
    col[x]=y;
    for(int i=0; i<G[x].size() && flag; i++)
        dfs(G[x][i],3-y);
}

void init(void)
{
    memset(col,0,sizeof(col));
    flag=true;
}

int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        init();
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1; i<=m; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        for(int i=1; i<=n; i++)
            if(!col[i])dfs(i,1);
        if(flag)printf("Correct\n");
        else printf("Wrong\n");
        for(int i=1;i<=n;i++)G[i].clear();
    }
    return 0;
}

最大匹配:

题目链接:最大匹配-匈牙利算法

dfs:

vector<int>G[1005];
bool vis[1005];
int m,n;
int match[1005];

bool dfs(int x)
{
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i];
        if(!vis[nex])
        {
            vis[nex]=true;
            if(!match[nex]||dfs(match[nex]))
            {
                match[nex]=x;
                match[x]=nex;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int x,y,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,false,sizeof(vis));
        if(!match[i]&&dfs(i))ans++;
    }
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)G[i].clear();
    return 0;
}

二维最大匹配:

题目链接:Antenna Placement

struct point
{
    int x,y;
};
char maze[50][50];
bool vis[50][50];
int m,n;
vector<point>vec[50][50];
point match[50][50];

void judgepoint(int x,int y)
{
    point t;
    if(x>1&&maze[x-1][y]=='*')
    {
        t.x=x-1;
        t.y=y;
        vec[x][y].push_back(t);
    }
    if(x<m&&maze[x+1][y]=='*')
    {
        t.x=x+1;
        t.y=y;
        vec[x][y].push_back(t);
    }
    if(y>1&&maze[x][y-1]=='*')
    {
        t.x=x;
        t.y=y-1;
        vec[x][y].push_back(t);
    }
    if(y<n&&maze[x][y+1]=='*')
    {
        t.x=x;
        t.y=y+1;
        vec[x][y].push_back(t);
    }
}

bool dfs(int x,int y)
{
    int len=vec[x][y].size();
    for(int i=0; i<len; i++)
    {
        point temp=vec[x][y][i];
        if(!vis[temp.x][temp.y])
        {
            vis[temp.x][temp.y]=1;
            if((!match[temp.x][temp.y].x&&!match[temp.x][temp.y].y)
                    ||dfs(match[temp.x][temp.y].x,match[temp.x][temp.y].y))
            {
                match[temp.x][temp.y].x=x;
                match[temp.x][temp.y].y=y;
                match[x][y].x=temp.x;
                match[x][y].y=temp.y;
                return true;
            }
        }
    }
    return false;
}

void init(void)
{
    memset(maze,0,sizeof(maze));
    memset(match,0,sizeof(match));
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d",&m,&n);
        for(int i=1; i<=m; i++)
            scanf("%s",maze[i]+1);
        for(int i=1; i<=m; i++)
            for(int j=1; j<=n; j++)
                if(maze[i][j]=='*')
                    judgepoint(i,j);
        int ans=0;
        for(int i=1; i<=m; i++)
            for(int j=1; j<=n; j++)
                if(maze[i][j]=='*'&&!match[i][j].x&&!match[i][j].y)
                {
                    memset(vis,0,sizeof(vis));
                    if(dfs(i,j))ans++;
                }

        for(int i=1; i<=m; i++)
            for(int j=1; j<=n; j++)
                if(maze[i][j]=='*'&&!match[i][j].x&&!match[i][j].y)
                    ans++;
        printf("%d\n",ans);
        for(int i=1; i<=m; i++)
            for(int j=1; j<=n; j++)
                if(maze[i][j]=='*')vec[i][j].clear();
    }
    return 0;
}

题目链接:最小点覆盖和最大独立集

最小点覆盖=最大匹配数

最大独立集=点数-最大匹配数

vector<int>G[1005];
bool vis[1005];
int m,n;
int match[1005];

bool dfs(int x)
{
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i];
        if(!vis[nex])
        {
            vis[nex]=true;
            if(!match[nex]||dfs(match[nex]))
            {
                match[nex]=x;
                match[x]=nex;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int x,y,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,false,sizeof(vis));
        if(!match[i]&&dfs(i))ans++;
    }
    printf("%d\n%d\n",ans,n-ans);
    for(int i=1;i<=n;i++)G[i].clear();
    return 0;
}

题目链接:最小路径覆盖

最小路径覆盖=点数-最大匹配数

vector<int>G[1005];
bool vis[1005];
int match[1005];

bool dfs(int x)
{
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i];
        if(!vis[nex])
        {
            vis[nex]=true;
            if(!match[nex]||dfs(match[nex]))
            {
                match[nex]=x;
                match[x]=nex;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int n,m,x,y,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(n+y);
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,false,sizeof(vis));
        if(!match[i]&&dfs(i))ans++;
    }
    printf("%d\n",n-ans);
    return 0;
}

题目链接:带权二分匹配

km:

int cost[305][305],lx[305],ly[305];
int match[305],d;
bool visx[305],visy[305];

bool dfs(int x,int ny)
{
    visx[x]=true;
    for(int y=1; y<=ny; y++)
    {
        if(visy[y])continue;
        int t=lx[x]+ly[y]-cost[x][y];
        if(!t)
        {
            visy[y]=true;
            if(!match[y] || dfs(match[y],ny))
                return match[y]=x;
        }
        else d=min(d,t);
    }
    return false;
}

int km(int nx,int ny)
{
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    memset(match,0,sizeof(match));
    for(int i=1; i<=nx; i++)
        for(int j=1; j<=ny; j++)
            lx[i]=max(lx[i],cost[i][j]);
    for(int x=1; x<=nx; x++)
        while(1)
        {
            d=inf;
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
            if(dfs(x,ny))break;
            if(d==inf)return -1;
            for(int x=1; x<=nx; x++)
                if(visx[x])lx[x]-=d;
            for(int y=1; y<=ny; y++)
                if(visy[y])ly[y]+=d;
        }
    int res=0;
    for(int y=1; y<=ny; y++)
        if(match[y])
            res+=cost[match[y]][y];
    return res;
}


int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                scanf("%d",&cost[i][j]);
        printf("%d\n",km(n,n));
    }
    return 0;
}