NOI2009[变换序列/transform]

膜拜了题解后写的,我是用的倒序匹配,如果想知道该怎么做,推荐看看这份题解

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-5-13

DESCRIPTION:

$DESCRIPTION

*/

#include <cstdio>

using std::FILE;

using std::fopen;

using std::fclose;

using std::fscanf;

using std::fprintf;

#include <cstring>

using std::memset;

 

class Application

{

      static const int MAXN=10000;

      static const int MAXDEGREE=2;

      static const int NOTMATCHED=-1;

      FILE* in;

      FILE* out;

      int N;

      int D[MAXN];

      int degree[MAXN];

      int edge[MAXN][MAXDEGREE];

      int match[MAXN*2];

      bool visited[MAXN*2];

      void addEdge(int u,int v)

      {

           edge[u][degree[u]++]=v+N;

      }

      void build_graph()

      {

           for (int i=0;i<N;i++)

           {

               int n=(i+D[i])%N;

               int m=(i-D[i]+N)%N;

               if (n==m) addEdge(i,n);

               else if (n<m)

               {

                    addEdge(i,n);

                    addEdge(i,m);

               }

               else if (n>m)

               {

                    addEdge(i,m);

                    addEdge(i,n);

               }

           }

      }

      bool find(int x)

      {

           for (int i=0,y;i<degree[x];i++)

               if (!visited[y=edge[x][i]])

               {

                  visited[y]=true;

                  if (match[y]==NOTMATCHED||find(match[y]))

                  {

                     match[x]=y;

                     match[y]=x;

                     return true;

                  }

               }

           return false;

      }

      public:

      Application(const char* input,const char* output)

                        :in(fopen(input,“r”)),out(fopen(output,“w”))

      {

                        fscanf(in,“%d”,&N);

                        for (int i=0;i<N;i++) fscanf(in,“%d”,D+i);

                        memset(degree,0,sizeof(degree));

                        memset(match,NOTMATCHED,sizeof(match));

      }

      ~Application()

      {

                    fclose(in);

                    fclose(out);

      }

      int run()

      {

          build_graph();

          for (int i=N;memset(visited,0,sizeof(visited)),i–;)

              if (!find(i))

              {

                 fprintf(out,“No Answer\n”);

                 return 0;

              }

          for (int i=0;i<N;i++)

              fprintf(out,“%d%c”,match[i]-N,i+1==N?’\n’:’ ‘);

          return 0;

      }

};

 

int main()

{

    Application app(“transform.in”,“transform.out”);

    return app.run();

}

 

留下评论

您的邮箱地址不会被公开。 必填项已用 * 标注