HDU3605-Escape(网络流+二进制缩点)

题目链接:HDU3605-Escape

题意:

有n个人,m个星球,每个人只能适应一定的星球,每个星球都有一个容纳量,问最多有多少人能够迁移到星球上。

题解:

裸的网络流,但是注意数据范围,n有1e5,m只有10,所以我们可以考虑二进制状态压缩,把对星球适应情况完全相同的人缩成1个点,这样就最多只有1024个点了,网络流即可。

注意:千万不能抄错板子,无数次死在dfs中把cur[u]抄成fir[u]。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1 << 15;
const int MAXM = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
vector<int> a[MAXN];
struct EDGE
{
    int v, w, nxt;
} edge[MAXM << 1];
int ecnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
    edge[ecnt].v = v, edge[ecnt].w = w, edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
    swap(u, v);
    edge[ecnt].v = v, edge[ecnt].w = 0, edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
int tot = 0;
int cur[MAXN], depth[MAXN];
int dfs(int u, int flow, int st, int ed)
{
    if (u == ed)
        return flow;
    for (int &i = cur[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        int w = edge[i].w;
        if (depth[v] == depth[u] + 1 && w)
        {
            int di = dfs(v, min(w, flow), st, ed);
            if (di)
            {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}
bool bfs(int st, int ed)
{
    queue<int> q;
    while (!q.empty())
        q.pop();
    memset(depth, 0, sizeof(depth));
    depth[st] = 1;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (depth[v] == 0 && w > 0)
            {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
    return depth[ed] > 0;
}
int dinic(int st, int ed)
{
    int sum = 0;
    while (bfs(st, ed))
    {
        for (int i = 0; i <= tot + m + 2; i++)
            cur[i] = fir[i];
        while (int temp = dfs(st, inf * 2, st, ed))
            sum += temp;
    }
    return sum;
}
int main()
{
    while (scanf("%d%d", &n, &m) == 2)
    {
        ecnt = 0;
        memset(fir, -1, sizeof(fir));
        for (int i = 0; i < (1 << m); i++)
            a[i].clear();
        tot = 1 << m;
        for (int i = 0; i < n; i++)
        {
            int temp = 0;
            for (int j = 0; j < m; j++)
            {
                int x;
                scanf("%d", &x);
                if (x)
                    temp += (1 << j);
            }
            a[temp].push_back(i);
        }
        for (int i = 0; i < (1 << m); i++)
        {
            int sz = a[i].size();
            addedge(tot + m + 1, i, sz);
            int x = i, p = 0;
            while (x)
            {
                p++;
                if (x % 2)
                    addedge(i, tot + p, sz);
                x /= 2;
            }
        }
        for (int i = 0; i < m; i++)
        {
            int x;
            scanf("%d", &x);
            addedge(tot + i + 1, tot + m + 2, x);
        }
        dinic(tot + m + 1, tot + m + 2) == n ? puts("YES") : puts("NO");
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。