暂时先学个一般图最大匹配的吧……权匹配好像有点复杂。

p.s. WC至今只补了1题，跪早已补完的某老司机。

http://www.csie.ntnu.edu.tw/~u91029/Matching.html

这篇讲得非常好。

就是搞清楚奇点有pre，偶点才会进队。缩花之后修改偶点的pre，把奇点改成偶点进队。

#include<set>
#include<map>
#include<cmath>
#include<string>
#include<cstdio>
#include<vector>
#include<cctype>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
using namespace std;

int IN()
{
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

typedef long long ll;
typedef double Db;
typedef pair<int,int> pii;

const int N=500+19,M=124750+19;
typedef int one[N];
struct Edge {int y,nxt;} E[M*2];
one Last,Q,mate,col,pre,fa,vis;
int n,m,cnt,f,w,Time,x,y,Ans;

int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}
void Link(int x,int y)
{
	E[cnt]=(Edge){y,Last[x]};Last[x]=cnt++;
	E[cnt]=(Edge){x,Last[y]};Last[y]=cnt++;
}

int LCA(int x,int y)
{
	Time++;
	for (;;swap(x,y))
		if (x=getf(x))
		{
			if (vis[x]==Time) return x;
			vis[x]=Time,x=pre[mate[x]];
		}
}
void blossom(int u,int v)
{
	for (int x,y;u!=v;u=y)
	{
		x=mate[u],y=pre[x];
		if (getf(y)!=v) pre[y]=x;
		if (col[x]==1) col[Q[++f]=x]=0;
		fa[getf(u)]=getf(x);
		fa[getf(x)]=getf(y);
	}
}
int Find(int S)
{
	memset(col,-1,sizeof(col));
	memset(pre,0,sizeof(pre));
	For(i,1,n+1) fa[i]=i;
	f=1,w=0;Q[1]=S;col[S]=0;
	while (f>w)
	{
		int x=Q[++w];
		for (int i=Last[x],y;~i;i=E[i].nxt)
		{
			y=E[i].y;
			if (getf(x)==getf(y)||y==mate[x]||col[y]==1) continue;
			if (col[y]==-1)
			{
				if (mate[y])
				{
					pre[y]=x;
					col[y]=1;
					col[Q[++f]=mate[y]]=0;
				} else
				{
					for (int z;x;y=z,x=pre[z]) z=mate[x],mate[x]=y,mate[y]=x;
					return 1;
				}
			} else if (col[y]==0)
			{
				int z=LCA(x,y);
				if (getf(x)!=z) pre[x]=y;
				if (getf(y)!=z) pre[y]=x;
				blossom(x,z);
				blossom(y,z);
			}
		}
	}
	return 0;
}

int main()
{
	memset(Last,-1,sizeof(Last));
	n=IN(),m=IN();
	For(i,0,m)
	{
		x=IN(),y=IN(),Link(x,y);
		if (!mate[x]&&!mate[y]) mate[x]=y,mate[y]=x,Ans++;
	}
	For(i,1,n+1) if (!mate[i]&&Find(i)) Ans++;
	printf("%d\n",Ans);
	For(i,1,n+1) printf("%d ",mate[i]);puts("");
}