1. 首页
2. 网络流
3. 本页

UVALive 4957 Fake scoreboard (最大流)

题意：~

思路：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PI;
const int INF = 0x3f3f3f3f;
const int MAXN = 1500;
const int MAXM = 15000;

struct Edge
{
    int to, next, cap, flow;
} edge[MAXM];
int tol;
int head[MAXN];
int gg[205][205];

void init()
{
    tol = 2;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int w, int rw = 0)
{
    edge[tol] = (Edge){v, head[u], w, 0};
    gg[u][v] = tol;
    head[u] = tol++;
    edge[tol] = (Edge){u, head[v], rw, 0};
    gg[v][u] = tol;
    head[v] = tol++;
}
int Q[MAXN];
int dep[MAXN], cur[MAXN], sta[MAXN];
bool bfs(int s, int t, int n)
{
    int front = 0, tail = 0;
    memset(dep, -1, sizeof(dep[0]) * (n + 1));
    dep[s] = 0;
    Q[tail++] = s;
    while(front < tail)
    {
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow && dep[v] == -1)
            {
                dep[v] = dep[u] + 1;
                if(v == t) return true;
                Q[tail++] = v;
            }
        }
    }
    return false;
}

int dinic(int s, int t, int n)
{
    int maxflow = 0;
    while(bfs(s, t, n))
    {
        for(int i = 0; i < n; ++i) cur[i] = head[i];
        int u = s, tail = 0;
        while(cur[s] != -1)
        {
            if(u == t)
            {
                int tp = INF;
                for(int i = tail - 1; i >= 0; i--)
                    tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
                maxflow += tp;
                for(int i = tail - 1; i >= 0; i--)
                {
                    edge[sta[i]].flow += tp;
                    edge[sta[i] ^ 1].flow -= tp;
                    if(edge[sta[i]].cap - edge[sta[i]].flow == 0)
                        tail = i;
                }
                u = edge[sta[tail] ^ 1].to;
            }
            else if(cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to])
            {
                sta[tail++] = cur[u];
                u = edge[cur[u]].to;
            }
            else
            {
                while(u != s && cur[u] == -1)
                    u = edge[sta[--tail] ^ 1].to;
                cur[u] = edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}

int a[100], b[100];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    bool ff = 0;
    while(cin >> n >> m)
    {
        if(n == 0 && m == 0) break;
        if(ff) cout << endl;
        ff = 1;
        int s1 = 0, s2 = 0;
        for(int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            s1 += a[i];
        }
        for(int i = 1; i <= m; ++i)
        {
            cin >> b[i];
            s2 += b[i];
        }
        if(s1 != s2)
        {
            cout << "Impossible" << endl;
            continue;
        }
        init();
        int st = 0, ed = n + m + 1;
        for(int i = 1; i <= n; i++)
        {
            addedge(st, i, a[i]);
            for(int j = 1; j <= m; j++) addedge(i, n + j, 1);
        }
        for(int i = 1; i <= m; i++)
        {
            addedge(n + i, ed, b[i]);
        }
        int ans = dinic(st, ed, n + m + 2);
        if(ans != s1)
        {
            cout << "Impossible" << endl;
            continue;
        }
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= m; ++j)
            {
                int to = gg[i][j + n];
                if(edge[to].cap == edge[to].flow)
                {
                    edge[gg[st][i]].cap++;
                    edge[gg[j + n][ed]].cap++;
                    if(dinic(st, ed, n + m + 2)) cout << "N";
                    else
                    {
                        edge[gg[st][i]].cap--;
                        edge[gg[j + n][ed]].cap--;
                        cout << "Y";
                    }
                }
                else
                {
                    edge[to].cap = 0;
                    cout << "N";
                }
            }
            cout << endl;
        }
    }
    
    return 0;
}