题目链接：https://cn.vjudge.net/problem/HDU-3605

题意：给你n个人，m个星球，每个人对这m个星球的都有一定的适应能力，每个星球都有一定的容纳量，问能否让所有的人在星球上生存。

刚开始做的时候一直TLE 不知道为什么，改着改着发现建图的时候，添了很多边，这样跑最大流非常慢，看了网上的思路才知道要缩点，因为星球最多才有10个，所以把每个星球适合住的人数存一下，当做源点与星球的边的流量，星球的最大容纳量当做星球与汇点的边的流量。

跑一遍dinic，最大流大于等于n即YES

否则NO

#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;

const int MAX = (1ll << 31) - 1;

struct Edge{
    int to;
    int dis;
    int next;
} edges[1100];

int cur[2001], head[2000], edge_num = -1;
int n, m, s, t;

void addEdge2(int from, int to, int dis){
    edges[++edge_num].to = to;
    edges[edge_num].dis = dis;
    edges[edge_num].next = head[from];
    head[from] = edge_num;
}

void addEdge(int from, int to, int dis){
    addEdge2(from, to, dis);
    addEdge2(to, from, 0);
}

int d[2001],e[100],p[100];

int DFS(int u, int flow){
    if (u == t) return flow;
    int _flow = 0, __flow;
    for (int& c_e = cur[u]; c_e != -1; c_e = edges[c_e].next){
        int v = edges[c_e].to;
        if (d[v] == d[u] + 1 && edges[c_e].dis > 0){
            __flow = DFS(v, min(flow, edges[c_e].dis));
            flow -= __flow;
            edges[c_e].dis -= __flow;
            _flow += __flow;
            edges[c_e^1].dis += __flow;
            if (!flow)
                break;
        }
    }
    if (!_flow) d[u] = -1;
    return _flow;
}

bool BFS(){
    for(int i=s;i<=t;i++) d[i] = -1;
    queue<int> que; que.push(s);
    d[s] = 0; int u, _new;

    while (!que.empty()){
        u = que.front(), que.pop();
        for (int i = head[u]; i != -1; i = edges[i].next){
            _new = edges[i].to;

            if (d[_new] == -1 && edges[i].dis > 0){
                d[_new] = d[u] + 1;
                que.push(_new);
            }
        }
    }
    return (d[t] != -1);
}

void dinic(){
    int max_flow = 0;

    while (BFS()){
        for (int i = s; i <= t; ++i) cur[i] = head[i];
        max_flow += DFS(s, MAX);
    }

    printf("%s\n", max_flow>=n?"YES":"NO");
}


int main(){
    while(scanf("%d%d",&n,&m)!=EOF) {
        int flag=0;
        memset(e,0,sizeof(e));
        for(int i=0;i<=100;i++) head[i] = -1;
        for(int i=1;i<=n;i++) {
            int sum=0,x;
            for(int j=0;j<m;j++) {
                scanf("%d",&x);
                if(x)  e[j]++,sum++;
            }
            if(!sum)flag=1;
        }
        for(int i=0;i<m;i++) {
            scanf("%d",&p[i]);
        }
        if(flag) {
            printf("NO\n");
            continue;
        }
        for(int i=0;i<m;i++) {
            if(e[i]) {
                addEdge(0,i+1,e[i]);
            }
            if(p[i]) {
                addEdge(i+1,m+1,p[i]);
            }
        }

        s = 0, t = m + 1;
        dinic();
    }

	return 0;
}

 

 

当然还有更简单的，直接求上图的最小割即为最大流，由于最小割就是每条增广路的饱和边之和

即ans += min(e[i], e[i + m]);

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>

using namespace std;

int n,m,x,nump[1050],p[15],e[30]; 

int solve()
{
   int ans=0;
   for (int i=0;i<m;i++) ans+=min(e[i],e[i+m]);
   return ans;
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(p,0,sizeof(p));
        memset(e,0,sizeof(e));
        int flag=0;
        for (int i=1;i<=n;i++)
        {
            int sum=0;
            for (int j=1;j<=m;j++)
            {
                scanf("%d",&x);
                if (x) e[j-1]++,sum++;
            }
            if(!sum)flag=1;
        }
        for (int i=0;i<m;i++) scanf("%d",&p[i]);
        if (flag)
        {
            printf("NO\n");
            continue;
        }
        for (int i=0;i<m;i++) if (p[i]) e[i+m]+=p[i];
        int ans=solve();
        if (ans>=n) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}