题目链接：
题意：求无向图最大匹配。
思路：带花树。
#include#include #include #include #define SET(a,b) memset(a,b,sizeof(a));using namespace std;const int MAX=230;queue Q;int g[MAX][MAX],inque[MAX],inblossom[MAX];int match[MAX],pre[MAX],set[MAX];int n;int findancestor(int u,int v){ int visit[MAX]={0}; while(1) { u=set[u]; visit[u]=1; if(match[u]==-1) break; u=pre[match[u]]; } while(1) { v=set[v]; if(visit[v]) break; v=pre[match[v]]; } return v;}void reset(int u,int root){ int v; while(u!=root) { v=match[u]; inblossom[set[u]]=1; inblossom[set[v]]=1; v=pre[v]; if(set[v]!=root) pre[v]=match[u]; u=v; }}void contract(int u,int v){ int root=findancestor(u,v); int i; SET(inblossom,0); reset(u,root); reset(v,root); if(set[u]!=root) pre[u]=v; if(set[v]!=root) pre[v]=u; for(i=1;i<=n;i++) if(inblossom[set[i]]) { set[i]=root; if(!inque[i]) Q.push(i),inque[i]=1; }}int BFS(int S){ int u,v,i,t; for(i=1;i<=n;i++)pre[i]=-1,inque[i]=0,set[i]=i; while(!Q.empty()) Q.pop(); Q.push(S); inque[S]=1; while(!Q.empty()) { u=Q.front(); Q.pop(); for(v=1;v<=n;v++)if(g[u][v]&&set[v]!=set[u]&&match[u]!=v) { if(v==S||match[v]!=-1&&pre[match[v]]!=-1) contract(u,v); else if(pre[v]==-1) { pre[v]=u; if(match[v]!=-1) { Q.push(match[v]); inque[match[v]]=1; } else { u=v; while(u!=-1) { v=pre[u]; t=match[v]; match[u]=v; match[v]=u; u=t; } return 1; } } } } return 0;}int solve(){ SET(match,-1); int i,ans=0; for(i=1;i<=n;i++) if(match[i]==-1&&BFS(i)) ans++; return ans;}int main(){ while(scanf("%d",&n)!=-1) { int i,u,v; SET(g,0); while(scanf("%d%d",&u,&v)!=-1)g[u][v]=g[v][u]=1; printf("%d\n",solve()*2); int visit[MAX]; SET(visit,0); for(i=1;i<=n;i++) if(!visit[i]&&match[i]!=-1) { printf("%d %d\n",i,match[i]); visit[i]=visit[match[i]]=1; } } return 0;}