题解 P2319 【[HNOI2006]超级英雄】

x_faraway_x · 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
}