自动搬运

查看原文

来自洛谷，原作者为

	x_faraway_x 毫无特色的 OI 入门选手

搬运于2025-08-24 21:36:19，当前版本为作者最后更新于2017-09-10 00:45:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

论仔细读题的重要性，千万不要一鸡冻“呀这题裸匈牙利”就码码码码玩了，结果尽管能过样例却只有20分……

这题唯一和模板不一样的就是你找不到匹配了就要立刻退出了……就这么一点小坑……

剩下来就是模板啦，所以这题提高+有点过了吧……

#include<cstdio>
#include<cstring>
const int N=1005;
bool to[N][N],vis[N];
int l[N],n,m,ans,sum[N]; 
bool Find(int x) //裸的匈牙利模版
{
    for(int j=1;j<=n;j++)
        if(to[x][j]&&!vis[j])
        {
            vis[j]=true;
            if(l[j]==0||Find(l[j]))
            {
                l[j]=x; sum[x]=j;
                return true;
            }
        }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        to[i][x+1]=to[i][y+1]=true; //将下标统一从1开始方便处理
    }
    for(int i=1;i<=m;i++)
    {
        memset(vis,false,sizeof(vis));
        if(Find(i))ans++;
        else break; //小坑：找不到就立即退出
    }
    printf("%d\n",ans);
    for(int i=1;i<=ans;i++) printf("%d\n",sum[i]-1); //这里最后答案-1，因为之前加了个1
}