HDU Escape (网络流，最大流)

                                                                    Escape

题目链接：click Here~

题目分析：

    在世界末日到来的时候，有n个地球人想跑到星星上去生活。而每个星星是不同的，且每个星星能容纳的人数是有限的。现在要求你求出这n个人能不能全部跑到星星上。一段时间不能跟某人聊天了，感觉很伤心。

算法分析：

    一开始直接，上手网络流求解。冏，后来编译器直接奔溃了，一看提示才发现不能直接暴力。因为数据n太大了，所以要另外想办法，可惜我没想到啊。后来，看了别人的才知道是二进制压缩（其实我也没完全懂）。自己可以看LRJ的白书，如果不是搞ACM的就算了，那个老师肯定不会教的。

    因为是网络流所以我们可以很显然的想到是否能用到二分匹配呢？显然这题是可以得。其实就是二分图中的完美匹配，用KM算法就好了。因为这题数据特殊，所以用一般的匈牙利算法就可以过。但是话说我交了20+都没过，冏。后来就懒的在交了。感兴趣的自己可以去找别人的博客。

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

const int MAXN = 1e4,INF = ~0U >> 1;
struct Edge{
   int from,to,cap,flow;
   Edge(int f,int t,int c,int _f)
       :from(f),to(t),cap(c),flow(_f){}
};
class MF{
public:
    void Init(int n,int m);
    bool Solve(int n,int m);
    void AddEdge(int from,int to,int cap);
    bool BFS();
    int DFS(int u,int a);
    int Maxflow();
    int Read();
private:
    vector<Edge> edges;
    vector<int> G[MAXN];
    int n,s,t;
    int d[MAXN],cur[MAXN];
    bool vst[MAXN];
};
void MF::Init(int n,int m)
{
    s = 0; t = (1<<m)+m+1;
    for(int i = 0;i <= t;++i)
        G[i].clear();
    edges.clear();
}
inline void MF::AddEdge(int from,int to,int cap)
{
    edges.push_back(Edge(from,to,cap,0));
    edges.push_back(Edge(to,from,0,0));
    int sz = edges.size();
    G[from].push_back(sz-2);
    G[to].push_back(sz-1);
}
bool MF::BFS()
{
    memset(vst,0,sizeof(vst));
    vst[s] = true; d[s] = 0;

    queue<int> Q;
    Q.push(s);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        for(int i = 0;i < (int)G[u].size();++i){
            Edge& e = edges[G[u][i]];
            if(!vst[e.to]&&e.cap > e.flow){
                vst[e.to] = true;
                d[e.to] = d[u]+1;
                Q.push(e.to);
            }
        }
    }
    return vst[t];
}
int MF::DFS(int u,int a)
{
    if(u==t||a==0)
        return a;
    int f,flow = 0;
    for(int& i = cur[u];i < (int)G[u].size();++i){
        Edge& e = edges[G[u][i]];
        if(d[e.to]==d[u]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){
            e.flow += f;
            edges[G[u][i]^1].flow -= f;
            flow += f;
            a -= f;
            if(a == 0)break;
        }
    }
    return flow;
}
int MF::Maxflow()
{
   int flow = 0;
   while(BFS()){
       memset(cur,0,sizeof(cur));
       flow += DFS(s,INF);
   }
   return flow;
}
bool MF::Solve(int n,int m)
{
    Init(n,m);
    int k,f,ope[MAXN]={0};
    for(int i = 1;i <= n;++i){
        k = 0;
        for(int j = 0;j < m;++j){
            f = Read();
            if(f) k += (1<<j);
        }
        ope[k]++;
    }
    for(int i = 1;i <= m;++i){
        f = Read();
        AddEdge((1<<m)+i,t,f);
    }
    for(int i = 0;i < (1<<m);++i){
        if(ope[i]==0)continue;
        AddEdge(s,i+1,ope[i]);
        for(int j = 0;j < m;++j){
            k = 1<<j;
            if(i&k) AddEdge(i+1,j+(1<<m)+1,ope[i]);
        }
    }
    return n <= Maxflow();
}
int MF::Read()
{
    char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    int sum = 0;
    while(isdigit(ch)){
        sum *= 10;
        sum += ch-‘0‘;
        ch = getchar();
    }
    return sum;
}
int main()
{
    int n,m;
    MF cf;
    while(~scanf("%d%d",&n,&m)){
        if(cf.Solve(n,m))
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

HDU Escape (网络流，最大流),布布扣,bubuko.com

HDU Escape (网络流，最大流)

原文：http://blog.csdn.net/zhongshijunacm/article/details/23299659