HDU 3605 dinic

题

HDU

解

题意：n个人在不超过10个星球中选择，而各个星球有一个人数上限。问能否全部适配。

星球比较少所以缩点咯。

码（3836K, 1201ms）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1 << 16, INF = 0x3f3f3f3f;
int s, t;
struct Edge
{
    int from, to, cap, flow;
};
vector<Edge> edges;
vector<int> G[maxn];
void add_edge(int from, int to, int cap)
{
    edges.push_back((Edge){from, to, cap, 0});
    edges.push_back((Edge){to, from, 0, 0});
    int m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
}
bool vis[maxn] = {false};
int d[maxn] = {0};
bool bfs()
{
    memset(vis, 0, sizeof vis);
    queue<int> Q;
    Q.push(s);
    d[s] = 0; vis[s] = true;
    while(!Q.empty())
    {
        int x = Q.front(); Q.pop();
        for(int i = 0; i < G[x].size(); i++)
        {
            Edge &e = edges[G[x][i]];
            if(!vis[e.to] && e.flow < e.cap)
            {
                vis[e.to] = true;
                d[e.to] = d[x] + 1;
                Q.push(e.to);
            }
        }
    }
    return vis[t];
}
int cur[maxn] = {0};
int dfs(int x, int a)
{
    if(x == t || a == 0)
        return a;
    int flow = 0, f;
    for(int &i = cur[x]; i < G[x].size(); i++)
    {
        Edge &e = edges[G[x][i]];
        if(d[e.to] == d[x] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0)
        {
            e.flow += f; edges[G[x][i] ^ 1].flow -= f, flow += f, a -= f;
            if(a == 0) break;
        }
    }
    return flow;
}
int maxflow()
{
    int flow = 0;
    while(bfs())
    {
        memset(cur, 0, sizeof cur);
        flow += dfs(s, INF);
    }
    return flow;
}
int cnt[2048] = {0};
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        memset(cnt, 0, sizeof cnt);
        edges.clear();
        for(int i = 0; i < 1040; i++)
            G[i].clear();
        for(int k = 0; k < n; k++)
        {
            int s = 0;
            for(int i = 0; i < m; i++)
            {
                int a; read(a);
                s <<= 1; s |= a;
            }
            cnt[s]++;
        }
        for(int i = 0; i < 1024; i++)
            if(cnt[i])
            {
                add_edge(1035, i, cnt[i]);
                int k = i;
                for(int j = m; j > 0; j--)
                {
                    int t = k % 2; k >>= 1;
                    if(t)
                        add_edge(i, 1024 + j, cnt[i]);
                }
            }
        for(int i = 1; i <= m; i++)
        {
            int a; read(a);
            add_edge(1024 + i, 1036, a);
        }
        s = 1035, t = 1036;
        printf("%s\n", maxflow() == n ? "YES" : "NO");
    }
    return 0;
}