社区讨论

大佬求助,58分

P3386【模板】二分图最大匹配参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi862fld
此快照首次捕获于
2025/11/21 09:13
4 个月前
此快照最后确认于
2025/11/21 09:13
4 个月前
查看原帖
58分
CPP
#include<cstdio>
#include<algorithm>
#include<cstring>
const int N = 1000010;
struct MyStruct{
    int x,y,next;
}a[N];	int last[N/10],len = 0, p[N];
bool v[N];
void ins(int x,int y)
{
    len++;
    a[len].x = x;
    a[len].y = y;
    a[len].next = last[x];
    last[x] = len;
    return;
}
bool go(int x)
{
    for(int k=last[x];k;k=a[k].next)
    {
        int y = a[k].y;
        if(v[y]==0)
        {
            v[y]=1;
            if(p[y] == 0 || go(p[y])==1)
            {
                p[y]=x;
                return 1;
            }
        }
    }	
    return 0;
}
int main()
{
    int n,m,k,ans=0;
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1,x,y;i<=k;i++)
    {
        scanf("%d %d",&x,&y);
        ins(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        memset(v,0,sizeof(v));
        go(i)==1?ans++:ans;
    }
    printf("%d",ans);
}

回复

6 条回复,欢迎继续交流。

正在加载回复...