CSU 1842: Fake scoreboard dinic(2010 Southwestern European Regional Contest)

1842: Fake scoreboard Submit Page    Summary    10 Sec 128 Mb 43 12

Description

　　As you know, after the award ceremony of SWERC it is customary to publish a complete scoreboard with detailed information on the submissions and verdicts received. However, due to the buggy contest management system, most of the relevant data are not being recorded today. Clearly such state of a airs fails to meet the high standards we are committed to, so the judges have resolved to make up the rest of the data based on whatever shred of information left, and hope contestants are unable to tell the difference. To make our lives even simpler, we kindly ask you to provide a solution for us, or else today's scoreboard will remain forever veiled in mystery (even the fake one).

　　What we will know by the end of the contest is the number T of teams, the number P of problems, and the number of accepted submissions by each team. From the number and colour of balloons floating around on the premises we will also be able to infer how many teams solved each of the problems. Your task is to　figure out which teams solved which problems.

1≤i≤T

1≤i≤T ), write the string on alphabet N,Y such that its j-th ( 1≤j≤P

1≤j≤P

NYY

NNY

YYN

There is at least one other solution, namely

NYY

NYN

YNY

　　When several solutions are possible we ask you to supply the one giving rise to the lexicographically smallest string, when each of the T rows are concatenated in order. In the example above we prefer the first solution, since NYYNNYYYN comes before NYYNYNYNY in lexicographical order. (String S comes before S' in lexicographical order if the first different character between the two is N in S but Y in S').

Input

1≤T,P≤80

1≤T,P≤80

Different input cases are separated by a blank line. The last line of the input file will be 0 0.

Output

　　If the input data has a solution, print T lines of P characters each, depicting the lexicographically smallest solution as explained above. Otherwise output a single line with the word Impossible. In any case a blank line should separate outputs for different test cases.

Sample Input

2 2

1 2

1 1

3 3

2 1 2

1 2 2

3 5

3 3 1

3 1 1 0 2

0 0

Sample Output

Impossible

NYY

NNY

YYN

YNYNY

YYNNY

YNNNN

        听alpc的学长说regional经常考网络流哦，所以说有一个好的模板很重要~~

        然后本题的话，如果仅仅只是判断方案的可行性的话，很裸的一个网络流模型。原模型应该是这样子的：告诉你行的和以及列的和（行和列只能填1和0），问是否存在符合要求的矩阵。其实呢，贪心好像就可以了，但是用上网络流模型的话会显得很优(zhuang)美(B)。构图也很简单，源点连接行，流量为行之和，列连接汇点，流量为列之和，然后每一行连接每一列，流量为1。在这个图上跑一边dinic就行了。为什么我钟爱dinic呢？这个等等再说。

        但是，这题并没有辣么简单，这题要求输出字典序最小的方案。我们发现，N的字典序小于Y，所以我们要尽量把N放在前面。那么问题出现了，我们如何判断某一个位置是否可以放N而不放Y呢？其实我也没想过暴力去判就能过。首先按字典序枚举位置(i，j)对应的边(i，j)，如果其残余流量为1，那么显然这里可以放N，并封死该边以及反向边。当残余流量不为1时，说明这条边用过了，那么我们就要看，如果封死这条边，是否还能再找到对应的一种解法。于是把这条变以及反向边封死，并且对相应的行和列分别增加一条与源汇相连流量为1的边，再在残余网络中找增广路，如果还能找到，说明这条边是多余的，可以放N。如果找不到增广路，显然只能放Y，并且记得擦屁股，把新添加的边封死。

        是的，就是这么暴力。然后为什么用dinic，当然是因为我的模板是非递归的超快的dinic，来自于alpc的政神Orz……

        然后这个模板是以邻接表的形式贮存图的，在这道题的条件中可能会慢一点，因为如果是邻接矩阵的话，我判定的时候只需要把对应的流量加一减一即可，而且删除的时候也更加方便。而且本题是稠密图，判定的时候使得边更加的多，邻接表每次枚举的时候都会拖慢速度。但这些都不重要，重要的是，这个dinic的模板还是跑了Rank1（速度并列，内存输了），实在是太快了啊，再次Orz……

#include<bits/stdc++.h>
#define MAX_V 200

using namespace std;

int n,m;

namespace MaxNetFlow
{
  struct Edge
  {
    int dest,cap;
    Edge *next,*pair;
    Edge() {}
    Edge(int _dest,int _cap,Edge* _next):dest(_dest),cap(_cap),next(_next){}
  };
  
  Edge *e[MAX_V],*c[MAX_V],*p[MAX_V];
  int Stack[MAX_V],Queue[MAX_V],dist[MAX_V];
  int s,t,maxflow,top;
  
  inline void clear()
  {
    memset(e,0,sizeof(e));
  }
    
  inline void addedge(int a,int b,int c)
  {
    e[a]=new Edge(b,c,e[a]);
    e[b]=new Edge(a,0,e[b]);
    e[a]->pair=e[b],e[b]->pair=e[a];
  }
  
  inline bool lab()
  {
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0; Queue[1]=s;
    for (int l=1,r=1;l<=r;l++)
    {
      int i=Queue[l];
      for (Edge *j=e[i];j;j=j->next)
      if (j->cap && dist[j->dest]>dist[i]+1)
      {
        dist[j->dest]=dist[i]+1;
        if (j->dest==t) return 1;
        Queue[++r]=j->dest;
      }
    }
    return 0;
  }
  
  inline void aug()
  {
    int top=0; Stack[++top]=s;
    memcpy(c,e,sizeof(e));
    while (top)
    {
      int i=Stack[top];
      if (i!=t)
      {
        Edge *j;
        for (j=c[i];j;j=j->next)
          if (j->cap && dist[j->dest]==dist[i]+1) break;
        if (j) top++,Stack[top]=j->dest,c[i]=p[top]=j;
        else top--,dist[i]=1e9;
      } else
      {
        int delta=1e9;
        for (int i=top;i>=2;i--)
          delta=std::min(delta,p[i]->cap);
        maxflow+=delta;
        for (int i=top;i>=2;i--)
        {
          p[i]->cap-=delta,p[i]->pair->cap+=delta;
          if (!p[i]->cap) top=i-1;
        }
      }
    }
  }
  
  inline int dinic()
  {
    maxflow=0;
    while (lab()) aug();
    return maxflow;
  }
  
  inline void BuildAnswer()
  {
    for(int i=1;i<=n;i++)
    {
      for(Edge *j=e[i];j;j=j->next)
      {
        if (j->dest==s || j->dest==t) continue;    //连向源汇的边当然不用产生答案
        bool flag=(j->cap);
        if (!flag)
        {
          addedge(s,i,1);
          addedge(j->dest,t,1);
          j->cap=j->pair->cap=0;      //尝试封死这条边
          dinic();      //看是否能找到增广路
          if (maxflow<=0) e[s]->cap=e[j->dest]->cap=0;  //找不到则封死新加的边
                 else flag=1;
        }
        j->cap=j->pair->cap=0;    //直接封死该边
        if (flag) putchar('N');
             else putchar('Y');
      }
      putchar('\n');
    }  
  }
}

int main()
{
  while (~scanf("%d%d",&n,&m) && n && m)
  {
    int sum1=0,sum2=0,c;
    MaxNetFlow::clear();
    int s=MaxNetFlow::s=0;
    for(int i=1;i<=n;i++)
    {
      scanf("%d",&c); sum1+=c;
      MaxNetFlow::addedge(s,i,c);
    }
    int t=MaxNetFlow::t=n+m+1;
    for(int i=1;i<=m;i++)
    {
      scanf("%d",&c); sum2+=c;
      MaxNetFlow::addedge(i+n,t,c);
    }
    for(int i=n;i>=1;i--)
      for(int j=m;j>=1;j--)      //因为BuildAnswer()遍历边的时候是按照先加入后遍历的
        MaxNetFlow::addedge(i,j+n,1);    //所以为了满足字典序，我们就从后往前加边
    MaxNetFlow::dinic();
    int maxflow=MaxNetFlow::maxflow;
    if (sum1!=sum2 || maxflow!=sum1) {puts("Impossible\n");continue;}
    MaxNetFlow::BuildAnswer();
    putchar('\n');
  }
}