Escape

题目：

   很裸的多重匹配。但是点数较多，所以要用到状态压缩。。。。。。

第一次写。好厉害的赶脚。

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

const int INF = 1 << 30;
const int MAXN = 20000 + 10;

//////////////////////////////
struct Edge{
   int from,to,cap,flow;
   Edge(){};
   Edge(int _from,int _to,int _cap,int _flow)
       :from(_from),to(_to),cap(_cap),flow(_flow){};
};
vector<Edge> edges;
vector<int> G[MAXN];
int d[MAXN],cur[MAXN];
int N,M,src,sink;

////////////////////////////

int dp[MAXN];

void init(){
    src = http://www.mamicode.com/(1 << M) + M + 2; sink = src + 1;>

 
试写了一个二分多重匹配，时间在该题上差不多。第一次写这个多重匹配，凭着感觉写了一个。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 100000 + 10;
int G[MAXN][15];
int match[15][MAXN],up[15],Link[15];
bool used[15];
int N,M;

bool dfs(int u){
   for(int v = 0;v < M;++v){
        if(G[u][v] && !used[v]){
            used[v] = 1;
            if(Link[v] < up[v]){
                match[v][Link[v]++] = u;
                return true;
            } else {
                for(int i = 0;i < Link[v];++i){
                    if(dfs(match[v][i])){
                       match[v][i] = u;
                       return true;
                    }
                }
            }
        }
   }

   return false;
}

void solve(){
    int res = 0;
    bool flag = false;
    memset(match,-1,sizeof(match));
    memset(Link,0,sizeof(Link));

    for(int i = 0;i < N;++i){
        memset(used,0,sizeof(used));
        if(!dfs(i)){
            res++;
            flag = true;        ///提前退出，反超时！！！！！！1
            break;
        }
    }
    if(flag){
        puts("NO");
    } else {
       puts("YES");
    }
}
int main()
{
  //  freopen("Input.txt","r",stdin);

    while(scanf("%d%d",&N,&M) == 2){
         memset(G,0,sizeof(G));
         for(int i = 0;i < N;++i){
            for(int j = 0;j < M;++j){
                scanf("%d",&G[i][j]);
            }
         }

         for(int i = 0;i < M;++i)
            scanf("%d",&up[i]);

         solve();
    }
    return 0;
}

 
 
 
hdu Escape