记录编号	557702	评测结果	AAAAWWWAAWWAAAAAAAAA
题目名称	2952.[SYOI 2018] 国政议事	最终得分	75
用户昵称	Evolt	是否通过	未通过
代码语言	C++	运行时间	0.299 s
提交时间	2020-11-23 20:33:47	内存使用	2.55 MiB

#include <cstdio>
#include <cstring>
#define maxn 505
#define maxm 20005
using namespace std;
int cur[maxm | 1] , ans , match[maxn << 1 | 1],head[maxn << 1 | 1],num_edge,n,m,a[maxn | 1],b[maxn | 1];
bool vis[maxn << 1 | 1];
struct edge{        
	int to,next;
	edge(){
		to = next = 0;
	}
}Edge[maxm | 1];
inline void add_edge(const int &from,const int &to){
	Edge[++ num_edge].next = head[from];
	Edge[num_edge].to = to;                    
	head[from] = num_edge;           
	return ;
}
inline bool find(const int &x) {
	for(int i = head[x];i;i = Edge[i].next){
		int v = Edge[i].to;                                              
		if(!v)continue ;
		if(vis[v])continue ;
		vis[v] = true;
		if(!match[v] || find(match[v])){
			match[v] = x;
			return true;
		}
	}
	return false;
}
inline int matched(void) {
	int cnt = 0;
	memset(match , 0 , sizeof(match));
	for(int i = 1;i <= n;++ i){
		memset(vis , false , sizeof(vis));
		cnt += find(i);
	}
	return cnt;          
}
int main(){
	freopen("pol_cov.in","r",stdin);
	freopen("pol_cov.out","w",stdout);
    scanf("%d%d",&n,&m);
	int u,v;                       
	for(int i = 1;i <= m;++ i){
	    scanf("%d%d",&u,&v);
		add_edge(u , v);
	}
	int tot = matched();
	printf("%d ",tot);
	int t;
	for(int i = 1;i <= m;++ i){
		t = Edge[i].to;
		Edge[i].to = 0;
		if(matched() != tot){
			cur[++ ans] = i;
		}
		Edge[i].to = t;
	}
	printf("%d\n",ans); 
	for(int i = 1;i <= ans;++ i){
	    printf("%d\n",cur[i]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}