TopCoder 10738 TheContest

谢谢 @dadaaa 帮助我看懂了这个题解。

官方题解做法：

一、

n \leq m

。

考虑已经填完了

x

行，再往下填一行。运用二分图匹配，左部点是格子，右部点是数，能连边当且仅当这个格子对应上去的一列还没有填这个数字。

可以证明一定能找到如此匹配。那怎么让字典序最小呢？每次进行一次“尝试连边”的时候需要用另一个匈牙利算法判一遍有没有解，有解就确定这条边，否则继续“尝试连边”。

二、

n>m

。

依然考虑已经填完了

x

行，再往下填一行。还是运用二分图匹配，左部点是格子，右部点是数，能连边当且仅当这个格子对应上去的一列还没有填这个数字。

但是这里按照上面的算法不一定能找到如此匹配。

左部点每个点的度数是

N-x

，右部点每个点度数可能大于

N-x

，这可怎么办？（此时就不能凑出

N-x

个匹配，即下面所有行的方案）暂且不要担心，在填写每一行的时候，每次进行一次“尝试连边”的时候需要用另一个匈牙利算法判一遍有没有所有的度数为 $N-x$ 的右部点都被匹配上了的解，有解就确定这条边，否则继续“尝试连边”。这样就不会出现右部点每个点度数大于

N-x

的情形了（也就找到了一组解）。

官方题解做法太难写了，我没写。

网络神秘博客做法：

n \leq m

依然同上，

n>m

的时候我们在左部添加

n-m

个虚点，把“不匹配”转化为“和虚点”匹配，度数为

N-x

的右部点则不与虚点连边，这样仍然是正确的！

CPP

#include<bits/stdc++.h>
using namespace std;
namespace gza{
	#define int long long
	#define pb push_back
	#define MT int TTT=R;while(TTT--)
	#define pc putchar
	#define R read()
	#define fo(i,a,b) for(int i=a;i<=b;i++)
	#define rep(i,a,b) for(int i=a;i>=b;i--)
	#define m1(a,b) memset(a,b,sizeof a)
	namespace IO
	{
		inline int read()
		{
		    int x=0;
		    char ch=getchar();
		    bool f=0;
		    while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
		    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		    if(f) x=-x;
		    return x;    
		}
		template<typename T> inline void write(T x)
		{
		    if(x<0) pc('-'),x=-x;
		    if(x>9) write(x/10);
		    pc(x%10+'0');
		}
	};
	using namespace IO;
	
	const int N=55;
	int n,m,k,now;
	int match[N],ans[N];
	int deg[N];
	bool vis[N],g[N][N];
	bool dfs1(int u)
	{
		if(vis[u]) return 0;
		vis[u]=1;
		fo(j,1,k) if(g[u][j]&&(!match[j]||dfs1(match[j])))
		{
			match[j]=u;
			return 1;
		}
		return 0;
	}
	bool dfs2(int u)
	{
		if(vis[u]) return 0;
		vis[u]=1;
		fo(j,1,k) if(g[u][j]&&(match[j]==now||(match[j]>now&&dfs2(match[j]))))
		{
			match[j]=u;
			return 1;
		}
		return 0;
	}
	void main(){
		n=R,m=R,k=max(n,m);
		fo(i,1,k) fo(j,1,k) g[i][j]=1;
		fo(line,1,n)//当前填哪一行
		{
			m1(match,0);
			fo(i,m+1,k) fo(j,1,k) g[i][j]=(deg[j]!=m-n+line-1);//取消了必须匹配的点向虚点的边
			fo(i,1,k) m1(vis,0),dfs1(i);
			fo(i,1,k) m1(vis,0),now=i,dfs2(i);//求一个最小字典序匹配
			fo(i,1,k) if(match[i]<=m) g[match[i]][i]=0,ans[match[i]]=i,deg[i]++;
			//枚举右部点，如果匹配的不是虚点
			fo(i,1,m)
			{
				if(ans[i]<=9) pc(ans[i]+'0');
				else if(ans[i]<=35) pc(ans[i]-10+'A');
				else pc(ans[i]-36+'a');
			}
			puts("");
		}
	}
}
signed main(){
	
	gza::main();
}

TopCoder 10738 TheContest

文章操作

官方题解做法太难写了，我没写。

相关推荐

评论

TopCoder 10738 TheContest