题目传送门

解题思路

将题目和锦囊妙计建边，然后对于每一个问题，都跑一次匈牙利，如果当前问题找不到与之配对的锦囊妙计，那么直接停止（因为题目说了答不出就不能往下答了）。

代码

#include<bits/stdc++.h>
using namespace std;int n,m,ans;
vector<int> e[100001];
int vis[100001],last[100001];
int an[100001];
bool dfs(int x,int k)
{if(vis[x]==k)return 0;vis[x]=k;for(auto y:e[x]){if(last[y]==0||dfs(last[y],k)){last[y]=x;an[x]=y;return 1;}}return 0;
}
int main()
{cin>>n>>m;int x,y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);x++,y++;e[i].push_back(x);e[i].push_back(y);}int ti=0;for(int i=1;i<=m;i++){ti++;if(dfs(i,ti))ans++;else break;}cout<<ans<<endl;for(int i=1;i<=m;i++)if(an[i])cout<<an[i]-1<<endl;
}