题目传送门
解题思路
将题目和锦囊妙计建边,然后对于每一个问题,都跑一次匈牙利,如果当前问题找不到与之配对的锦囊妙计,那么直接停止(因为题目说了答不出就不能往下答了)。
代码
#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;
}