1 条题解
-
1
#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 }
- 1
信息
- ID
- 1270
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 7
- 已通过
- 2
- 上传者