一般図最大マッチング(ツリー付きアルゴリズム)(学習+テンプレート)

参考ブログ:
https://blog.csdn.net/xuezhongfenfei/article/details/10148445
https://www.cnblogs.com/zhoushuyu/p/8717234.html
https://www.cnblogs.com/owenyu/p/6858508.html
古典的な例題:
https://www.cnblogs.com/BAJimH/p/10569418.html
[拡張パスの反転]:2分の1マップマッチングで拡張パスの順序は、非一致エッジ-->一致エッジ>非一致エッジ->一致エッジ->...->非一致エッジ.逆にすると、非一致エッジが一致エッジになり、一致エッジが非一致エッジになります.
自分の理解:コアアルゴリズムはやはり拡張路を探していますが、一般的な図には奇環が存在する可能性があるので、拡張路を探すときは、1つの辺に2回関連する可能性があります.これにより、パスを広げて逆を取ることができず、マッチングの数を増やすことができます.1つの奇環にk(k>=3)個の点がある場合、内部点が一致すると、1つの点が一致しないことに気づきましたが、どうすればいいのでしょうか.リング外のポイントマッチングを探します.では、1つの奇環について、彼は1つの点しか一致していないので、私たちは奇環を1つの点(通称開花)に縮めました.どうやって縮めますか?、ここではメンテナンスを使用して収集します.しかし,奇環中のどの点で環外点を探して最大マッチングが得られるかを特定できないため,環中の点を列挙する.また、輪の中に輪(花の中に花がある)がある可能性があります.私たちは増広路を見つけるたびに、輪を次々と展開する必要があります.
具体的な流れは(上の大物ブログの):
私たちはすべての点を白黒で染めます.広がり始めた点が黒点だと仮定します.すべての黒い点をキューに押し込んで順番に処理します.黒い点uについて、彼と隣接する点vを探すと、4つの状況が現れます.
1、u、vはもう一つの点に縮められ(この二つの点は一つの花の中にある)、飛び越えた.
2、vは白点で、説明はすでに一致して、つまり偶環で、スキップします.
3、vはまだ染色されていません.では、まずこの点を白く染めて、uとマッチングしてみましょう.vがまだ一致していない場合は一致し、広がりは成功し、広がりに沿って反転します.vがマッチングされている場合、マッチングされた点は黒い点であり、染色され、キューに押し込まれます.
4、vも黒点です.この時染色が衝突し、奇環に出会ったことを示した.この場合、花木付きlcaの2つの点を見つけて、このリング全体を1つの点に縮める必要があります.△直接花を咲かせる.
縮点(開花)過程:1、xとyのLCA(の根)Lを探す.LCAを探すにはいろいろな方法が使えます...直接地味でもいいです.2、pre配列でxとyをつなぎます(リングを形成していることを示します!)3、x、yからそれぞれLまで歩いて、メンテナンスして集めて1本の木になるようにして、同時に道に沿ってpre配列を接続します.
例題1:uoj 29#79.一般図最大一致
一般図の最大一致を求めて、そして方案を出力します.

#include 
#define ll long long
using namespace std;
const int N = 510;
const int M = 3e5+10;
struct node{ int to,nxt; }g[M];
int head[N],cnt;
int vis[N],match[N],f[N],pre[N],Id,id[N];
//vis[i]: 0(   ) 1(  ) 2(  )
//match[i]: i    
//f[i]: i        
//pre[i]: i          
//id:  LCA  
int n,m,ans,u,v;
queue q;
void Init()
{
	Id=ans=cnt=0;
	for(int i=1;i<=n;i++)
		head[i]=-1,id[i]=match[i]=0;
}
void add(int u,int v){ g[cnt]=node{v,head[u]},head[u]=cnt++; }
int getf(int x){ return f[x]==x?x:f[x]=getf(f[x]); }
//  x y      LCA 
int LCA(int x,int y)
{
	//        lca 
	for(++Id;;swap(x,y))//x,y     
		if(x)
		{
			x=getf(x);//       (    )，         ，        
			if(id[x]==Id) return x; //x,y     ，           ，    LCA。 
			else id[x]=Id,x=pre[match[x]];//    ，          		
		}
}
//  （  ）， x、y LCA(l)     ，     
void blossom(int x,int y,int l)
{ 
	while(getf(x)!=l)
	{
		//      
		pre[x]=y,y=match[x];
		//  x、y       ，      ，    ，            	
		if(vis[y]==2) vis[y]=1,q.push(y);
		//        
		if(getf(x)==x) f[x]=l;
		if(getf(y)==y) f[y]=l;
		//      
		x=pre[y];
	} 
}
bool aug(int s)
{
	//    s   bfs，     
	for(int i=1;i<=n;i++)
		vis[i]=pre[i]=0,f[i]=i;	
	while(!q.empty()) q.pop();
	
	q.push(s),vis[s]=1;
	while(!q.empty())
	{
		u=q.front();q.pop();
		for(int i=head[u];~i;i=g[i].nxt)
		{
			v=g[i].to;
			//         ( )      (         )，     
			//            
			if(getf(u)==getf(v)||vis[v]==2) continue;
			//        
			if(!vis[v])
			{
				//     ，      u 
				vis[v]=2,pre[v]=u;
				//        ，       
				if(!match[v])
				{
					//      
					for(int x=v,last;x;x=last)
						last=match[pre[x]],match[x]=pre[x],match[pre[x]]=x;		
					return 1;
				}
				//      ，    v      ，     	
				vis[match[v]]=1,q.push(match[v]);
			}
			//v   ，    ，   (  )。 
			else 
			{
				 
				int lca=LCA(u,v);
				blossom(u,v,lca),blossom(v,u,lca);
			}
		}	
	}
	return 0;
}
int main(void)
{
	while(~scanf("%d%d",&n,&m))	
	{
		Init();
		while(m--)
		{
			scanf("%d%d",&u,&v);
			add(u,v),add(v,u);	
		}        
		for(int i=1;i<=n;i++)
			if(!match[i]&&aug(i))
				ans++;	
		printf("%d
",ans);
		for(int i=1;i<=n;i++)
			printf("%d%c",match[i]," 
"[i==n]);
	}
	return 0;	
} 

例題2:zoj 3316 Game
タイトル:1つの碁盤にはn個の駒があり、2人でゲームをし、持った駒と前の取られた駒のマンハッタンの距離はLを超えてはならず、後手に勝つことができるかどうかを聞く.
考え方:最大マッチングがnに等しいときに勝つことができて、さもなくば負けます.

#include 
#define ll long long
using namespace std;
const int N = 400;
const int M = 2e5+10;
struct node{ int to,nxt; }g[M];
struct Node{ int x,y; }a[N];
int head[N],cnt;
int vis[N],pre[N],f[N],match[N],id[N],Id;
queue q;
int n,L,ans,u,v;
void Init()
{
	ans=Id=cnt=0;
	for(int i=1;i<=n;i++)
		head[i]=-1,id[i]=match[i]=0;
}

void add(int u,int v) { g[cnt]=node{v,head[u]},head[u]=cnt++; }
int getf(int x){ return f[x]==x?x:f[x]=getf(f[x]); };
int LCA(int x,int y)
{
	for(++Id;;swap(x,y))
		if(x)
		{
			x=getf(x);
			if(id[x]==Id) return x;
			else id[x]=Id,x=pre[match[x]];
		}
}
void blossom(int x,int y,int l)
{
	while(getf(x)!=l)
	{
		pre[x]=y,y=match[x];
		if(vis[y]==2) vis[y]=1,q.push(y);
		if(getf(x)==x) f[x]=l;
		if(getf(y)==y) f[y]=l;
		x=pre[y];
	}
	
}

bool bfs(int s)
{
	for(int i=1;i<=n;i++)
		vis[i]=pre[i]=0,f[i]=i;
	while(!q.empty()) q.pop();
	q.push(s);vis[s]=1;
	while(!q.empty())
	{
		u=q.front();q.pop();
		for(int i=head[u];~i;i=g[i].nxt)
		{
			v=g[i].to; 
			if(getf(u)==getf(v)||vis[v]==2) continue;
			if(!vis[v])
			{
				vis[v]=2,pre[v]=u;
				if(!match[v])
				{
					for(int x=v,last;x;x=last)
						last=match[pre[x]],match[x]=pre[x],match[pre[x]]=x;
					return 1;
				}
				vis[match[v]]=1,q.push(match[v]);
			}
			else
			{
				int lca=LCA(u,v);
				blossom(u,v,lca),blossom(v,u,lca);
			}
		}
	}
	return 0;
}
int main(void)
{
	while(~scanf("%d",&n))
	{
		Init();
		for(int i=1;i<=n;i++)
			scanf("%d%d",&a[i].x,&a[i].y);	
		scanf("%d",&L);
		for(int i=1;i<=n;i++)
			for(int j=1;j