【题解】BZOJ4883: [Lydsy1705月赛]棋盘上的守卫(最小生成基环森林)

【题解】BZOJ4883: [Lydsy1705月赛]棋盘上的守卫(最小生成基环森林)

神题

我的想法是，每行每列都要有匹配且一个点只能匹配一个，于是就把格点和每行每列建点出来做一个最小生成树，但是不幸的是，这样子无法控制一个点是否选择多次，并且无法控制那些不需要变成守卫的点的情况

然后我看了题解..

一个元素的两种状态可以对应上一条边的方向，现在问题就变成了要选出一些边使得所有点的入度为1。也就是一个外向基环森林，直接类似克鲁斯卡尔做就行了。

这貌似可以抽象成一种模型，也就是有待选点，匹配点，待选点匹配点只能选择且必须选择一个待选点，一个待选点只能选择一个匹配点，同一个点任意选择匹配代价一样。若可以接受\(O(\prod P_i)\)的复杂度其中\(P\)代表一种匹配点的个数，那么就可以这样考虑给边定向构成外向基环森林来做。

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(!isdigit(c))f|=c==45,c=getchar();

      while(isdigit(c)) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=1e6+5;

struct E{

	int u,v,w;

	inline bool operator <(const E&a){return w<a.w;}

};

vector<E> e;

int n,m,cnt;

ll w;

inline void add(const int&fr,const int&to,const int&w){e.push_back({fr,to,w});}

int r[maxn*3],siz[maxn*3],c[maxn*3];

inline int q(const int&x){

	int t=x,i=x,temp;

	while(t^r[t]) t=r[t];

	while(i^r[i]) temp=r[i],r[i]=t,siz[t]+=siz[i],siz[i]=0,c[t]|=c[i],c[i]=0,i=temp;

	return t;

}

inline void J(int x,int y){

	if(siz[q(x)]>siz[q(y)])swap(x,y);

	r[q(x)]=q(y);  q(x);

}

int main(){

#ifndef ONLINE_JUDGE

      freopen("cpp.in","r",stdin);

      freopen("cpp.out","w",stdout);

#endif

	n=qr(); m=qr();

	cnt=n+m;

	for(int t=1;t<=n;++t)

		for(int i=1,u;i<=m;++i)

			u=qr(),add(t,i+n,u);

	for(int t=1;t<=cnt;++t) r[t]=t,siz[t]=1;

	sort(e.begin(),e.end());

	for(int t=0,ed=e.size();t<ed;++t){

		int u=q(e[t].v),v=q(e[t].u);

		if(!c[u]||!c[v]){

			//printf("%d %d\n",u,v);

			if(u==v) c[u]=c[v]=1;

			J(u,v),w=w+e[t].w;

		}

	}

	printf("%lld\n",w);

	cerr<<"w = "<<w<<endl;

	return 0;

}