spoj2142 Arranging Flowers

传送门

题目大意

给你n和m，表示一个n*n的数独已经填完了m行，让你填出剩下几行，要求答案的字典序最小。

分析

看到这道题我首先想到的是记录每行每列使用了哪些数字，然后贪心的来填，但是发现用这种策略会在有些情况下得不到解。于是我们考虑二分图匹配，将左边n个点表示每一行n个位置，右边n个点表示对应的n个数，我们一行一行的填，每填一行，便将产生的对应关系所代表的边删掉。那我们考虑如何二分图匹配可以得到字典序最小的答案，我们先进行一边常规的二分图匹配，然后枚举1到n每一个位置，找所有现在比位置j对应的值小且位置在j之后的k替换现在j对应的值，检测是否可以替换。注意这里的used数组只需每个j清空一次，因为j是一个固定的值，所以之前不行的值，随着k的改变仍然不行。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define li long long

#define pb push_back

#define mp make_pair

#define y1 y12345678909

#define rii register int

#define pii pair<int,int>

#define r(x) scanf("%d",&x)

#define ck(x) cout<<x<<endl;

#define uli unsigned long long

#define clr(x) memset(x,0,sizeof(x))

#define sp cout<<"------------------------------------------------------"<<endl

int g[],nxt[][],pre[][],belong[],T,used[],n,m,back[];

inline void del(int x,int y){

      if(g[x]==y)g[x]=nxt[x][y];

        else {

          nxt[x][pre[x][y]]=nxt[x][y];

          pre[x][nxt[x][y]]=pre[x][y];

        }

      return;

}

inline bool work(int x,int lit){

      for(rii i=g[x];i;i=nxt[x][i])

        if(used[i]!=T){

          used[i]=T;

          if(!belong[i]||(belong[i]>lit&&work(belong[i],lit))){

              belong[i]=x;

              back[x]=i;

              return ;

          }

        }

      return ;

}

inline void go(){

      for(rii i=;i<=n;++i){

          T++;

          work(i,);

      }

      for(rii j=;j<=n;++j){

          T++;

        for(rii k=g[j];k;k=nxt[j][k]){

            if(belong[k]==j)break;

            if(belong[k]<j)continue;

            int x=belong[k],y=back[j];

            belong[back[j]]=;

            back[belong[k]]=;

            belong[k]=j;

            back[j]=k;

            if(work(x,j))break;

            back[x]=k;

            belong[k]=x;

            belong[y]=j;

            back[j]=y;

        }

      }

      return;

}

int main(){

      int i,j,k,t,x;

      r(t);

      while(t--){

        r(n),r(m);

        clr(pre),clr(nxt);

        for(rii i=;i<=n;++i){

          g[i]=;

          int now=;

          for(rii j=;j<=n;++j){

              nxt[i][now]=j;

              pre[i][j]=now;

              now=j;

          }

        }

        for(rii i=;i<=m;++i)

          for(rii j=;j<=n;++j){

              r(x);

              del(j,x);

          }

        ck(n-m);

        for(rii i=m+;i<=n;++i){

          T=;

          clr(back);

          clr(belong);

          clr(used);

          go();

          for(rii j=;j<=n;++j)

            del(j,back[j]);

          for(rii j=;j<=n;++j)printf("%d ",back[j]);

          puts("");

        }

      }

      return ;

}