题解 UVA1104 【芯片难题 Chips Challenge】

· · 题解

\Large\color{#FFBBFF}\textit{Tian-Xing's blog}

Description

传送门

Solution

因为每一行最多方的芯片数量是随着芯片总数量变化的，这样不好整，所以我们枚举最大数量，用网络流跑出此时最多放置多少芯片如果比我们枚举的最大数量是合法的，就更新答案。

建立a_i表示行，建立b_i表示列。

从S向a_i连容量为该行可放置芯片数量和已经放好的芯片数量的和，费用为0的有向边。

从b_i向T连容量为该行可放置芯片数量和已经放好的芯片数量的和，费用为0的有向边，

从a_i向b_i连容量为枚举的最大数量，费用为0的有向边，如果流过这条边代表放置芯片。

如果一个位置(i, j)可以放置芯片，那么从a_i向b_j连容量为1，费用为1的有向边，如果流过这条边表示这个位置不放置芯片。

这样建模之后跑最小费用最大流，最大流限制了对每个位置都会进行放和不放的决策，最小费用保证了求出的方案不放的数量最少即放的芯片数量最多。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int INF = 999999999;
const int N = 1000050;
const int M = 2000050;

int n, s, t, head[N], cur[N], d[N], vis[N], num = 1, cnt, y[N], ans, maxflow, mincost, a, b, maxt, sum, hav, cd[5050], rd[5050];

char st[5050][5050];

struct Node
{
    int next, to, flow, dis;
} edge[M * 2];

void Addedge(int u, int v, int w, int c)
{
    edge[++num] = (Node){ head[u], v, w, c};
    head[u] = num;
}

void Add(int u, int v, int w, int c)
{
    Addedge(u, v, w, c);
    Addedge(v, u, 0, -c);
    return; 
}

template <class T>
void Read(T &x)
{
    x = 0; int p = 0; char st = getchar();
    while (st < '0' || st > '9') p = (st == '-'), st = getchar();
    while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
    x = p ? -x : x;
    return;
}

template <class T>
void Put(T x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) Put(x / 10);
    putchar(x % 10 + '0');
    return; 
}

int Bfs()
{
    queue<int> q;
    for (int i = 0; i <= t; i++) d[i] = INF, vis[i] = 0;
    d[s] = 0; vis[s] = 1; q.push(s);
    while (!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for (int i = head[u]; i; i = edge[i].next)
            if (edge[i].flow > 0 && d[edge[i].to] > d[u] + edge[i].dis)
            {
                d[edge[i].to] = d[u] + edge[i].dis;
                if (!vis[edge[i].to])
                {
                    vis[edge[i].to] = 1;
                    q.push(edge[i].to);
                }
            }   
    } 
    return d[t] != INF;
}

int Dinic(int x, int flow)
{
    if (x == t || !flow) return flow;
    int rest = flow, k;
    vis[x] = 1;
    for (int i = cur[x]; i && rest; i = edge[i].next)
    {
        int v = edge[i].to;
        cur[x] = i;
        if (!vis[edge[i].to] && edge[i].flow > 0 && d[edge[i].to] == d[x] + edge[i].dis)
        {
            int v = edge[i].to;
            int k = Dinic(v, min(rest, edge[i].flow));
        //  if (!k) dis[edge[i].to] = INF;
            rest -= k;
            edge[i].flow -= k;
            edge[i ^ 1].flow += k;
            mincost += k * edge[i].dis;
        }
    }
    vis[x] = 0;
    return flow - rest;
}

void Solve()
{
    while(Bfs())
    {
        for (int i = 0; i <= t; i++) cur[i] = head[i]; 
        maxflow += Dinic(s, INF);
    }
    return; 
}

int main()
{
    int tmp = 0;
    while (scanf("%d%d%d", &n, &a, &b) == 3)
    {
        if (!n) return 0;
        printf("Case %d: ", ++tmp);
        s = 0; t = n * 2 + 1;
        sum = 0; ans = -1; hav = 0;
        memset(rd, 0, sizeof (rd));
        memset(cd, 0, sizeof (cd));
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", st[i] + 1);
            for (int j = 1; j <= n; j++)
            {
                if (st[i][j] == 'C' || st[i][j] == '.')
                {
                    sum++; cd[i]++; rd[j]++;
                    if (st[i][j] == 'C') hav++;
                }
            }
        }
        for (int maxt = 0; maxt <= n; maxt++)
        {
            num = 1; memset(head, 0, sizeof(head));
            for (int i = 1; i <= n; i++)
            {
                Add(s, i, cd[i], 0);
                Add(i, i + n, maxt, 0);
                Add(i + n, t, rd[i], 0);
                for (int  j = 1; j <= n; j++)
                    if (st[i][j] == '.') Add(i, j + n, 1, 1);
            }
            maxflow = mincost = 0;
            Solve();
            if (maxflow == sum && (maxflow - mincost) * a >= maxt * b) ans = max(ans, maxflow - mincost);
        }
        if (~ans) printf("%d\n", ans - hav);
        else puts("impossible");
    }
    return 0;
}