HDU Escape (網絡流，最大流)

Escape

題目鏈接：click Here~

題目分析：

在世界末日到來的時候，有n個地球人想跑到星星上去生活。而每個星星是不同的，且每個星星能容納的人數是有限的。現在要求你求出這n個人能不能全部跑到星星上。一段時間不能跟某人聊天了，感覺很傷心。

算法分析：

一開始直接，上手網絡流求解。冏，後來編譯器直接奔潰了，一看提示才發現不能直接暴力。因為數據n太大了，所以要另外想辦法，可惜我沒想到啊。後來，看了別人的才知道是二進制壓縮（其實我也沒完全懂）。自己可以看LRJ的白書，如果不是搞ACM的就算了，那個老師肯定不會教的。

因為是網絡流所以我們可以很顯然的想到是否能用到二分匹配呢？顯然這題是可以得。其實就是二分圖中的完美匹配，用KM算法就好了。因為這題數據特殊，所以用一般的匈牙利算法就可以過。但是話說我交了20+都沒過，冏。後來就懶的在交了。感興趣的自己可以去找別人的博客。

#include 
#include 
#include 
#include 
#include 
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 edges;
    vector 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< 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<