TopCoder 10738 TheContest
luogu_gza
·
·
个人记录
谢谢 @dadaaa 帮助我看懂了这个题解。
官方题解做法：
一、n \leq m。
考虑已经填完了 x 行，再往下填一行。运用二分图匹配，左部点是格子，右部点是数，能连边当且仅当这个格子对应上去的一列还没有填这个数字。
可以证明一定能找到如此匹配。那怎么让字典序最小呢？每次进行一次“尝试连边”的时候需要用另一个匈牙利算法判一遍有没有解，有解就确定这条边，否则继续“尝试连边”。
二、n>m。
依然考虑已经填完了 x 行，再往下填一行。还是运用二分图匹配，左部点是格子，右部点是数，能连边当且仅当这个格子对应上去的一列还没有填这个数字。
但是这里按照上面的算法不一定能找到如此匹配。
左部点每个点的度数是 N-x，右部点每个点度数可能大于 N-x，这可怎么办？（此时就不能凑出 N-x 个匹配，即下面所有行的方案）暂且不要担心，在填写每一行的时候，每次进行一次“尝试连边”的时候需要用另一个匈牙利算法判一遍有没有所有的度数为 N-x 的右部点都被匹配上了的解，有解就确定这条边，否则继续“尝试连边”。这样就不会出现右部点每个点度数大于 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();
}
```