1. 题目

传送门= ̄ω ̄=

2. 题解

二分图最大匹配裸题

网络流偷懒打了匈牙利。

代码:

#include <bits/stdc++.h>
using namespace std;
int n,m,match[105],ans;
bool book[105];
vector<int> g[105];
bool dfs(int a)
{
    for(int i=0;i<g[a].size();i++)if(!book[g[a][i]])
    {
        book[g[a][i]]=1;
        if(!match[g[a][i]]){match[a]=g[a][i],match[g[a][i]]=a;return 1;}
        if(dfs(match[g[a][i]])){match[a]=g[a][i],match[g[a][i]]=a;return 1;}
    }
    return 0;
}
int main()
{
    scanf("%d%d",&m,&n),m-=n;
    int a,b;
    while(~scanf("%d%d",&a,&b))g[a].push_back(b),g[b].push_back(a);
    for(int i=1;i<=n;i++)if(!match[n])
        memset(book,0,sizeof(book)),ans+=dfs(i);
    printf("%d\n",ans);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *