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

#include <cstdio>
#include <cstring>
#define maxn 505
#define maxm 20005
const int INF = 0x3f3f3f3f;
using namespace std;      
int cur[maxm << 1 | 1] , ans = 0 , match[maxn << 1 | 1],head[maxn << 1 | 1],num_edge = 0,n,m,a[maxn << 1 | 1],b[maxn << 1 | 1];
bool vis[maxn << 1 | 1];
struct edge{                        
	int to,next;
	edge(){
		to = next = 0;
	}     
}Edge[maxm << 1 | 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 == INF)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 , -1 , sizeof(match));
	for(int i = n;i >= 1;-- 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 = INF;
		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;
}