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<