codeforces 739D

这题码量好大……

首先思考如何构造，不难找到一下两个条件

1. 在长度为i的环上的点一定是i的倍数个

2. 到达长度i的环的点集距离一定是连续的

第一个条件是很好搞的，关键是第二个条件。

因为存在着x ?这样的点，我们不知道到达环长度为i的点precycle能会连续延伸

但是观察可知，我们只要找出x ?类点中x最大的点xmax，穷举最终走到环的长度，

这样其他比xmax小的x ?点肯定都接到这个环上最有可能出解，那么到达每种环长度的precycle界限就确定了

这样我们就可以建图匹配来判定是否可行了，一侧条件一侧点连边看是否满流即可。

找出条件点流向的点，我们就能确定这些点的?是什么了

那么还有些点没用到应该怎么替换?呢

? ?的点直接构造一元环，x ?接在可行处，? x直接零?为1

而我们确定所有点的precycle和cycle后，是很容易构造最终出边的：

只要把环建好，其他在环上一个点下挂成一个简单树形即可

思路不难，写起来比较麻烦

 #include<bits/stdc++.h>

 #define mp make_pair

 using namespace std;

 const int inf=;

 struct way{int po,next,flow;} e[];

 pair<int,int> q[];

 int len,n,m,t,mx,pre[],numh[],cur[],h[],d[],p[];

 int w[][],hs[][],a[],b[],r[],ans[];

 vector<int> g[][];

 string s;

 bool v[];

 void add(int x,int y,int f)

 {

      e[++len].po=y;

      e[len].flow=f;

      e[len].next=p[x];

      p[x]=len;

 }

 void build(int x, int y, int f)

 {

      add(x,y,f);

      add(y,x,);

 }

 int sap()

 {

     memset(h,,sizeof(h));

     memset(numh,,sizeof(numh));

     numh[]=t+;

     for (int i=; i<=t; i++) cur[i]=p[i];

     int j,u=,s=,neck=inf;

     while (h[]<t+)

     {

           d[u]=neck;

           bool ch=;

           for (int i=cur[u]; i!=-; i=e[i].next)

           {

               j=e[i].po;

               if (e[i].flow>&&h[u]==h[j]+)

               {

                  neck=min(neck,e[i].flow);

                  cur[u]=i;

                  pre[j]=u;  u=j;

                  if (u==t)

                  {

                     s+=neck;

                     while (u)

                     {

                           u=pre[u];

                           j=cur[u];

                           e[j].flow-=neck;

                           e[j^].flow+=neck;

                     }

                     neck=inf;

                  }

                  ch=;

                  break;

               }

           }

           if (ch)

           {

              if (--numh[h[u]]==) return s;

              int q=-,tmp=t;

              for (int i=p[u]; i!=-; i=e[i].next)

              {

                  j=e[i].po;

                  if (e[i].flow&&h[j]<tmp)

                  {

                     tmp=h[j];

                     q=i;

                  }

              }

              cur[u]=q; h[u]=tmp+;

              numh[h[u]]++;

              if (u)

              {

                 u=pre[u];

                 neck=d[u];

              }

           }

     }

     return s;

 }

 bool check()

 {

     t=n; len=-;

     memset(p,,sizeof(p));

     memset(v,,sizeof(v));

     memset(hs,,sizeof(hs));

     for (int i=; i<=n; i++) v[b[i]]=;

     int can=;

     for (int i=; i<=n; i++)

         if (v[i])

         {

             int x=;

             if (!w[i][]) x=i;

             else x=i-(w[i][]-)%i-;

             if (x)

             {

                 hs[i][]=++t; q[t]=mp(i,);

                 build(,t,x); can+=x;

             }

             for (int j=; j<r[i]; j++)

                 if (!w[i][j])

                 {

                     hs[i][j]=++t; q[t]=mp(i,j);

                     build(,t,); can++;

                 }

         }

     for (int i=; i<=n; i++)

     {

         if (a[i]<n+&&b[i]<n+) continue;

         if (a[i]==n+&&b[i]==n+)

         {

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

                 build(j,i,);

         }

         else if (b[i]==n+)

         {

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

                 if (hs[j][a[i]]) build(hs[j][a[i]],i,);

         }

         else if (a[i]==n+)

         {

             for (int j=; j<r[b[i]]; j++)

                 if (hs[b[i]][j]) build(hs[b[i]][j],i,);

         }

         build(i,t+,);

     }

     t++;

     if (sap()<can) return ; else return ;

 }

 void print()

 {

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

         for (int j=p[i]; j>-; j=e[j].next)

         {

             int x=e[j].po;

             if (x&&x<=n&&!e[j].flow)

             {

                 a[x]=q[i].second;

                 b[x]=q[i].first;

             }

         }

   //  for (int i=1; i<=n; i++) cout <<a[i]<<" "<<b[i]<<endl;

     for (int i=; i<=n; i++)

         if (a[i]==n+&&b[i]==n+) {a[i]=; b[i]=;}

         else if (a[i]==n+) {a[i]=;}

         else if (b[i]==n+)

         {

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

                 if (r[j]>=a[i]) {b[i]=j; break;}

         }

     for (int i=; i<=n; i++)

         g[b[i]][a[i]].push_back(i);

     for (int i=; i<=n; i++)

     {

         for (int j=; j<g[i][].size(); j+=i)

         {

             for (int k=j; k<j+i-; k++) ans[g[i][][k]]=g[i][][k+];

             ans[g[i][][j+i-]]=g[i][][j];

         }

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

             for (int k=; k<g[i][j].size(); k++)

                 ans[g[i][j][k]]=g[i][j-][];

     }

     for (int i=; i<=n; i++) printf("%d ",ans[i]);

 }

 int main()

 {

     scanf("%d\n",&n);

     mx=;

     for (int i=; i<=n; i++)

     {

         getline(cin,s);

         int l=s.length(),j;

         for (j=; j<l; j++)

         {

             if (s[j]=='?') a[i]=n+;

             else if (s[j]==' ') break;

             else a[i]=a[i]*+s[j]-'';

         }

         j++;

         for (; j<l; j++)

         {

             if (s[j]=='?') b[i]=n+;

             else if (s[j]==' ') break;

             else b[i]=b[i]*+s[j]-'';

         }

         if (a[i]<n+&&b[i]==n+)

         {

             if (a[mx]<a[i]) mx=i;

         }

         else w[b[i]][a[i]]++;

     }

     for (int i=; i<=n; i++)

         for (int j=n; j; j--)

             if (w[i][j]) {r[i]=j; break;}

     bool ff=;

     for (int i=; i<=n; i++)

     {

         int pr=r[i];

         if (r[i]<a[mx])

         {

             r[i]=a[mx];

             b[mx]=i;

         }

         if (check()) {ff=;break;}

         b[mx]=n+; r[i]=pr;

     }

     if (!ff) puts("-1"); else print();

     return ;

 }

巴特西

codeforces 739D

最新文章

热门文章