题意就是有n个队伍和m个题目
给出了每个队伍解决的题目数量
每个题目也给出了被解决的次数
然后求一个方阵。
N，Y表示每个队伍是否过了哪个题目。
要求字典序最小。
这题给人的第一反应就是网络流。
虽然用网络流并不是最优算法。
但绝对是最直观的。
行和列分成两部分点。
源点向行连边。
行向列连边
列向终点连边
就行了
然后字典序要求最小。
那么就要枚举删边了。
我们先跑一遍网络流
然后从方阵左上角开始枚举。
每到一个枚举的位置，如果这个位置在第一次跑的网络流中就没有流量的话。显然这个位置可以放N
如果这个位置跑流量了，就要试着删边找增广了
将此边删除。 然后建两个新的源和汇。
源向行标号连一个1容量的边
列标号向新的汇连一个1容量的边
然后我们求新源汇的最大流
如若流量大于0，说明找到增光，此边可删，就删掉边，这个位置放N
否则这位置就Y。 不过同样把边删掉，以防以后找增广找到这。
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>
#define eps 1e-8
#define MAXN 366
#define MAXM 51111
#define INF 111111111
using namespace std ;
int nt, m;
int t[MAXN], p[MAXN];
struct Edge
{
int v, next;
int w;
}edge[MAXM];
int head[MAXN], e;
int id[MAXN][MAXN];
void init()
{
memset(head, -1, sizeof(head));
e = 0;
}
inline void add(int u, int v, int w)
{
edge[e].v = v;
edge[e].w = w;
edge[e].next = head[u];
head[u] = e++;
edge[e].v = u;
edge[e].w = 0;
edge[e].next = head[v];
head[v] = e++;
}
int h[MAXN], gap[MAXN];
int src, des, n;
int dfs(int pos, int cost)
{
if(pos == des) return cost;
int j, minh = n - 1;
int lv = cost, d;
for(j = head[pos]; j != -1; j = edge[j].next)
{
int v = edge[j].v;
int w = edge[j].w;
if(w > 0)
{
if(h[v] + 1 == h[pos])
{
if(lv < edge[j].w) d = lv;
else d = edge[j].w;
d = dfs(v, d);
edge[j].w -= d;
edge[j ^ 1].w += d;
lv -= d;
if(h[src] >= n) return cost - lv;
if(lv == 0) break;
}
if(h[v] < minh) minh = h[v];
}
}
if(lv == cost)
{
--gap[h[pos]];
if(gap[h[pos]] == 0) h[src] = n;
h[pos] = minh + 1;
++gap[h[pos]];
}
return cost - lv;
}
int sap()
{
int ret = 0;
memset(gap, 0, sizeof(gap));
memset(h, 0, sizeof(h));
//gap[0] = n;
while(h[src] < n) ret += dfs(src, INF);
return ret;
}
char out[MAXN][MAXN];
int S, T;
bool ok(int t1, int t2)
{
int k = id[t1][t2];
if(edge[k].w == 1)
{
edge[k].w = 0;
return true;
}
edge[k ^ 1].w = 0;
src = S;
des = T;
int e1 = e;
add(S, t1, 1);
int e2 = e;
add(t2 + nt, T, 1);
if(sap()){
edge[e1 ^ 1].w = edge[e2 ^ 1].w = 0;
return true;
}
edge[e1].w = edge[e2].w = 0;
return false;
}
int main()
{
//freopen("C:/D.in", "r", stdin);
//freopen("C:/DD.out", "w", stdout);
int cas = 0;
while(scanf("%d%d", &nt, &m) != EOF)
{
if(nt == 0 && m == 0) break;
if(cas) puts("");
cas++;
int sum1 = 0, sum2 = 0;
init();
for(int i = 1; i <= nt; i++)
{
scanf("%d", &t[i]);
sum1 += t[i];
}
for(int j = 1; j <= m; j++)
{
scanf("%d", &p[j]);
sum2 += p[j];
}
if(sum1 != sum2)
{
puts("Impossible");
continue;
}
src = nt + m + 1;
des = nt + m + 2;
S = nt + m + 3;
T = nt + m + 4;
n = T;
for(int i = 1; i <= nt; i++)
for(int j = 1; j <= m; j++)
{
id[i][j] = e;
add(i, j + nt, 1);
}
for(int i = 1; i <= nt; i++)
add(src, i, t[i]);
for(int i = 1; i <= m; i++)
add(i + nt, des, p[i]);
int ans = sap();
if(ans != sum1)
{
puts("Impossible");
continue;
}
for(int i = 1; i <= nt; i++)
for(int j = 1; j <= m; j++)
{
if(ok(i, j)) putchar('N');
else putchar('Y');
if(j == m) printf("
");
}
}
return 0;
}