同SCOI2010 游戏。
#include<iostream> #include<cstdio> #include<cstring> #define maxv 2050 #define maxe 200050 using namespace std; struct edge { int v,nxt; }e[maxe]; int n,m,a,b,g[maxv],nume=0,vis[maxv],linker[maxv]; void addedge(int u,int v) { e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume; } bool dfs(int u) { for (int i=g[u];i;i=e[i].nxt) { int v=e[i].v; if (vis[v]==1) continue; vis[v]=1; if ((linker[v]==-1)||(dfs(linker[v]))) { linker[v]=u; return true; } } return false; } int main() { memset(linker,-1,sizeof(linker)); scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d",&a,&b); addedge(i,a+1); addedge(i,b+1); } int ans=0; for (int i=1;i<=m;i++) { memset(vis,0,sizeof(vis)); if (dfs(i)) ans++; else break; } printf("%d ",ans); return 0; }