GYM102268 Angle Beats(一般图匹配)

GYM102268 Angle Beats(一般图匹配) GYM102268 Angle Beats(一般图匹配)

给定 n × m ntimes m n×m矩阵

一个+能与四周两个.匹配，一个*只能与两个.围成为 L L L型，即这两个.共一个顶点。输出最多匹配的方案。

考虑拆点，把+,*拆两个点，然后+ 的两个点与四周的.连边，把* 的两个点分别连上左右和上下的.，这样保证*的两个点有匹配时 一定是匹配L。

然后就是输出方案，如果对于.或者*，如果两个点均有匹配，且匹配不是他们两个，就染色，染色注意判四周是否已经染过色了，选用一个没用的字母即可。

时间复杂度： O ( n m ) O(nm) O(nm) 这里 n , m n,m n,m 是实际结点和实际边数。

#include
using namespace std;
typedef long long ll;
const int N=5e4+5,M=105,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair
#define fi first
#define se second
#define mst(a,b) memset(a,b,sizeof a)
struct Blossom_Tree{
    vectore[N];
    queueq;
    int mh[N],pre[N],s[N],id[N],vis[N],n,num;
    void init(int nn){	//初始化 
        n=nn,num=0;
        for(int i=1;i<=n;i++) e[i].clear(),mh[i]=pre[i]=vis[i]=s[i]=id[i]=0;
    }
    void add(int u,int v){
        e[u].push_back(v),e[v].push_back(u);
    }
    int find(int x){ return s[x]==x?x:s[x]=find(s[x]);}
    int LCA(int x,int y){	//求LCA. 
    for(++num;;swap(x,y))
        if(x){
        if(id[x=find(x)]==num) return x;//在同一个奇环肯定能找到被编号的结点. 
        id[x]=num,x=pre[mh[x]];	//沿增广路径的非匹配边向上走直到找到祖先. 
    }
    }
    void blossom(int x,int y,int rt){	//缩点(开花)  O(n)
        while(find(x)!=rt){
            pre[x]=y,y=mh[x];
            if(vis[y]==2) vis[y]=1,q.push(y);//如果奇环上有2型结点 就变为1型结点加入队列. 
            if(find(x)==x) s[x]=rt;//只对根处理. 
            if(find(y)==y) s[y]=rt;
            x=pre[y];
        }
    }
    bool aug(int st){	//求增广路径.O(n) 
    for(int i=1;i<=n;i++) vis[i]=pre[i]=0,s[i]=i; 
    while(!q.empty()) q.pop();
    q.push(st),vis[st]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(auto v:e[u]){
            if(find(u)==find(v)||vis[v]==2) continue;//如果是已经缩点了或者是偶环直接继续，没有影响. 
            if(!vis[v]){	//如果没有被染色 
                vis[v]=2,pre[v]=u;
                if(!mh[v]){	//如果未被匹配，就进行匹配 
                    for(int x=v,last;x;x=last)	//增广路取反 
                        last=mh[pre[x]],mh[x]=pre[x],mh[pre[x]]=x;
                    return 1;
                }
                vis[mh[v]]=1,q.push(mh[v]); //否则将v的匹配结点染色，加入队列. 
            }
            else{
             int rt=LCA(u,v);	//找到LCA ,然后进行缩点. 
             blossom(u,v,rt),blossom(v,u,rt);
            }
        }
    }
    return 0;
    }
    void cal(){
        int ans=0;
        for(int i=1;i<=n;i++) if(!mh[i]&&aug(i)) ans++;	//最大匹配. 
       // return ans;
       //printf("ans=%dn",ans);
    }
}T;
int n,m;
char a[M][M];
int c1[M][M],c2[M][M];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
bool used[26];
void color(int x,int y){
	for(int i=0;i<4;i++){
		int nx=x+dir[i][0],ny=y+dir[i][1];
		if(a[nx][ny]>='a'&&a[nx][ny]<='z') used[a[nx][ny]-'a']=true;
	}
}
char get_chr(int x,int y){
	mst(used,0);
	color(x,y);
	for(int i=0;i<4;i++){
		int nx=x+dir[i][0],ny=y+dir[i][1];
		if(T.mh[c1[x][y]]==c1[nx][ny]||T.mh[c2[x][y]]==c1[nx][ny]) 
			color(nx,ny);
		
	}
	for(int i=0;i<26;i++) if(!used[i]) return i+'a';
}
void solve(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='+'||a[i][j]=='*'){
		if(T.mh[c1[i][j]]==c2[i][j]||!T.mh[c2[i][j]]||!T.mh[c1[i][j]]){
			continue;
		}
		char ch = get_chr(i,j);
		a[i][j]=ch;
		for(int k=0;k<4;k++){
			int nx=i+dir[k][0],ny=j+dir[k][1];
			if(T.mh[c1[nx][ny]]==c1[i][j]||T.mh[c1[nx][ny]]==c2[i][j]){
				a[nx][ny]=ch;
			}
		}
			}
		}
	}
	for(int i=1;i<=n;i++) printf("%sn",a[i]+1);
}
int main(){
	scanf("%d%d",&n,&m);
	int sz=0;
	for(int i=1;i<=n;i++){
		scanf("%s",a[i]+1);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='.') c1[i][j]=++sz;
			else c1[i][j]=++sz,c2[i][j]=++sz,T.add(sz-1,sz);
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(a[i][j]=='*'){
				if(a[i][j-1]=='.') T.add(c1[i][j],c1[i][j-1]);
				if(a[i][j+1]=='.') T.add(c1[i][j],c1[i][j+1]);
				if(a[i-1][j]=='.') T.add(c2[i][j],c1[i-1][j]);
				if(a[i+1][j]=='.') T.add(c2[i][j],c1[i+1][j]);
			}else if(a[i][j]=='+'){
				for(int k=0;k<4;k++){
					int x=i+dir[k][0],y=j+dir[k][1];
					if(a[x][y]=='.') 
					T.add(c1[i][j],c1[x][y]),T.add(c2[i][j],c1[x][y]);		
				}
			}
		}
	T.n=sz;
	T.cal();
	solve();
    return 0;
}