学步园

Breaking news! A Russian billionaire has bought a yet undisclosed NBA team. He's planning to invest huge effort and money into making that team the best. And
in fact he's been very specific about the expected result: the first place.

Being his advisor, you need to determine whether it's possible for your team to finish first in its division or not.

More formally, the NBA regular season is organized as follows: all teams play some games, in each game one team wins and one team loses. Teams are grouped
into divisions, some games are between the teams in the same division, and some are between the teams in different divisions.

Given the current score and the total number of remaining games for each team of your division, and the number of remaining games between each pair of teams
in your division, determine if it's possible for your team to score at least as much wins as any other team in your division.

The first line of input contains N (2
≤ N ≤ 20) — the number of teams in your
division. They are numbered from 1 to N,
your team has number 1.

The second line of input contains N integers w₁, w₂,..., w_N,
where w_i is
the total number of games that i^th team
has won to the moment.

The third line of input contains N integers r₁, r₂,..., r_N,
where r_i is
the total number of remaining games for the i^th team
(including the games inside the division).

The next N lines
contain N integers each. The j^th integer
in the i^th line
of those contains a_ij —
the number of games remaining between teams i and j.
It is always true that a_ij=a_ji and a_ii=0,
for all i a_i1 + a_i2 +...
+ a_iN ≤ r_i.

All the numbers in input are non-negative and don't exceed 10\,000.

On the only line of output, print "

YES

" (without quotes) if it's possible for the team 1 to score at least as much wins as any other team of its division, and "

NO

" (without quotes) otherwise.

sample input

sample output

3
1 2 2
1 1 1
0 0 0
0 0 0
0 0 0

YES

sample input

sample output

3
1 2 2
1 1 1
0 0 0
0 0 1
0 1 0

NO

题目：http://acm.sgu.ru/problem.php?contest=0&problem=326

分析：这题与这题一样，就不具体分析了。。。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int oo=1000000000;
const int mm=6666;
const int mn=1111;
int node,edge,src,dest;
int ver[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn],w[mn];
int t[22][22];
void prepare(int _node,int _src,int _dest)
{
    node=_node,src=_src,dest=_dest;
    for(int i=0;i<node;++i)head[i]=-1;
    edge=0;
}

void addedge(int u,int v,int c)
{
    ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
    ver[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
int Dinic_bfs()
{
    int i,u,v,l,r=0;
    for(i=0;i<node;++i)dis[i]=-1;
    dis[q[r++]=src]=0;
    for(l=0;l<r;++l)
        for(i=head[u=q[l]];i>=0;i=next[i])
            if(flow[i]&&dis[v=ver[i]]<0)
            {
                dis[q[r++]=v]=dis[u]+1;
                if(v==dest)return 1;
            }
    return 0;
}
int Dinic_dfs(int u,int exp)
{
    if(u==dest)return exp;
    for(int &i=work[u],v,tmp;i>=0;i=next[i])
        if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
        {
            flow[i]-=tmp;
            flow[i^1]+=tmp;
            return tmp;
        }
    return 0;
}
int Dinic_flow()
{
    int i,ret=0,delta;
    while(Dinic_bfs())
    {
        for(i=0;i<node;++i)work[i]=head[i];
        if(delta=Dinic_dfs(src,oo))ret+=delta;
    }
    return ret;
}
int main()
{
    int i,j,m,n,sum,r;
    while(scanf("%d",&n)!=-1)
    {
        for(i=1;i<=n;++i)scanf("%d",&w[i]);
        scanf("%d",&r);
        w[1]+=r;
        for(i=1;i<n;++i)scanf("%d",&r);
        m=0;
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
            {
                scanf("%d",&t[i][j]);
                if(i>1&&i<j&&t[i][j])++m;
            }
        prepare(n+m+2,0,n+m+1);
        sum=r=0;
        for(i=2;i<=n;++i)
            for(j=i+1;j<=n;++j)
                if(t[i][j])
                {
                    sum+=t[i][j];
                    ++r;
                    addedge(src,r,t[i][j]);
                    addedge(r,m+i,oo);
                    addedge(r,m+j,oo);
                }
        for(i=2;i<=n;++i)
        {
            if(w[i]>w[1])break;
            addedge(m+i,dest,w[1]-w[i]);
        }
        if(i>n&&Dinic_flow()==sum)puts("YES");
        else puts("NO");
    }
    return 0;
}