题目链接：https://vjudge.net/problem/SGU-326

题意：NBA 某小组内有 N 支球队，小组内以及小组间已经进行了若干场比赛。现在给出这 N 支球队目前胜利的场数、还剩多少场没有比（包括小组内和小组间）以及小组内任意两支球队之间还剩多少场没有比,存在maze[i][j]中， 问能否合理安排剩下的所有比赛，使得球队 1 最后胜利的场数至少和小组内任何一支其他球队一样。 （2 <= N <= 20,0 <= x <= 10000, x 表示其他任何输入）

解法：本题略神，题解描述来自：http://blog.csdn.net/qq_26564523/article/details/50562412   首先，所有和球队1相关的比赛都让1赢，胜场记为win=w[1]+r[1]（已经赢得加上还剩下的比赛），如果已经此时仍然有球队胜利的场数大于球队1，那不管怎么挣扎，就算让这个球队剩下的比赛全输，球队1都不可能赢了对吧。除了1的其他球队所有组间赛都让他输（组间赛的场数可求，因为告诉了r[i]和组内的剩下比赛），组内赛再说。既然约定与球队1相关的比赛都是1赢，那么剩下的比赛中与1相关的比赛就不用管了，都已经是1赢了，调整不了了，因为每个球队已经有过胜场，那么要使球队1拿第一，那么其他球队i在剩下的比赛赢场最多为win-w[i]。

现在可以开始建图了，我们把点分为几类：源点，汇点，球队（除球队1），比赛（除开和1有关的比赛）。 首先，源点向每个球队连一条边，容量为该球队最多胜场（win-w[i]），因为每个球队接下来还要打比赛，所以对于某次比赛maze[i][j]（其中i!=1,j!=1)，我们让i和j分别与此次比赛连边，容量都为inf，或者maze[i][j]，再把此次比赛与汇点连一条边，容量为maze[i][j]，每场比赛都用一个特定的数值代替就可以建图了。最后，sum记录和球队1无关的所有组内赛总数（因为我们建图全是组内赛，组间赛已经让他们输了，没必要考虑），看看跑出的最大流是否等于sum，如果等于那么可以调整让球队1 赢，因为其他球队的剩下的比赛不管输赢都正常进行了。


我的建图源点和汇点上面的方法反了一下，但是思路是一样的。


#include <bits/stdc++.h>
using namespace std;
const int maxn = 1110;
const int maxm = 100010;
const int inf = 0x3f3f3f3f;
struct G
{
    int v, cap, next;
    G() {}
    G(int v, int cap, int next) : v(v), cap(cap), next(next) {}
} E[maxm];
int p[maxn], T;
int d[maxn], temp_p[maxn], qw[maxn]; //d顶点到源点的距离标号,temp_p当前狐优化，qw队列
void init()
{
    memset(p, -1, sizeof(p));
    T = 0;
}
void add(int u, int v, int cap)
{
    E[T] = G(v, cap, p[u]);
    p[u] = T++;
    E[T] = G(u, 0, p[v]);
    p[v] = T++;
}
bool bfs(int st, int en, int n)
{
    int i, u, v, head, tail;
    for(i = 0; i <= n; i++) d[i] = -1;
    head = tail = 0;
    d[st] = 0;
    qw[tail] = st;
    while(head <= tail)
    {
        u = qw[head++];
        for(i = p[u]; i + 1; i = E[i].next)
        {
            v = E[i].v;
            if(d[v] == -1 && E[i].cap > 0)
            {
                d[v] = d[u] + 1;
                qw[++tail] = v;
            }
        }
    }
    return (d[en] != -1);
}
int dfs(int u, int en, int f)
{
    if(u == en || f == 0) return f;
    int flow = 0, temp;
    for(; temp_p[u] + 1; temp_p[u] = E[temp_p[u]].next)
    {
        G& e = E[temp_p[u]];
        if(d[u] + 1 == d[e.v])
        {
            temp = dfs(e.v, en, min(f, e.cap));
            if(temp > 0)
            {
                e.cap -= temp;
                E[temp_p[u] ^ 1].cap += temp;
                flow += temp;
                f -= temp;
                if(f == 0)  break;
            }
        }
    }
    return flow;
}
int dinic(int st, int en, int n)
{
    int i, ans = 0;
    while(bfs(st, en, n))
    {
        for(i = 0; i <= n; i++) temp_p[i] = p[i];
        ans += dfs(st, en, inf);
    }
    return ans;
}
int n, w[maxn], r[maxn], maze[maxn][maxn];

int main(){
    while(scanf("%d", &n) != EOF)
    {
        int sounce = 0, sink = 1000;
        for(int i=1; i<=n; i++) scanf("%d", &w[i]);
        for(int i=1; i<=n; i++) scanf("%d", &r[i]);
        int win = w[1]+r[1], sum = 0, flag = 1;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                  scanf("%d", &maze[i][j]);
        init();
        for(int i=2; i<=n; i++){
            if(win-w[i]<0){//如果某支球队已经赢得场数都大于球队1最大可能赢得场数，那么GG，怎么也不可能赢了
                flag = 0;
                break;
            }
            add(i+400, sink, win-w[i]);
        }
        if(flag == 0){
            puts("NO");
            continue;
        }
        for(int i=2; i<=n; i++){
            for(int j=i+1; j<=n; j++){
                if(maze[i][j]<=0) continue;
                sum += maze[i][j]; //比赛场数
                add(sounce, (i-1)*n+j, maze[i][j]);
                add((i-1)*n+j, i+400, inf);
                add((i-1)*n+j, j+400, inf);
            }
        }
        int ans = dinic(sounce, sink, sink+1);
        if(ans == sum) puts("YES");
        else puts("NO");
    }
    return 0;
}