求救 WA#8
查看原帖
求救 WA#8
12755
星河·莫楼主2019/4/16 22:09
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,gs[200+5],love[200+5][200+5],bf,p[200+5],vis[200+5],p2,ans;
bool change(int wz)
{
    if (vis[wz]) return 0;
    vis[wz]=1;
    for (int j=1;j<=gs[wz];j++)
    if (p[love[wz][j]]==0) {p[love[wz][j]]=wz;return 1;}
    for (int j=1;j<=gs[wz];j++)
    {
        bf=p[love[wz][j]];
        p[love[wz][j]]=wz;
        if (change(bf)) return 1;
        p[love[wz][j]]=bf;
    }
    vis[wz]=0;
    return 0;
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&gs[i]);
        for (int j=1;j<=gs[i];j++)
        scanf("%d",&love[i][j]);
    }
    for (int i=1;i<=n;i++)
    {
        p2=0;
        for (int j=1;j<=gs[i];j++)
        if (p[love[i][j]]==0) {p2=1;p[love[i][j]]=i;break;}
        if (p2==0)
        for (int j=1;j<=gs[i];j++)
        {
            bf=p[love[i][j]];
            p[love[i][j]]=i;
            if (change(bf)) {p2=1;break;}
            p[love[i][j]]=bf;
        }
        ans+=p2;
    }
    cout<<ans<<endl;
}
2019/4/16 22:09
加载中...