326. Perspective

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



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.

Input
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 1, w 2,..., 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 1, r 2,..., 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.

Output
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.

Example(s) 
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



又是积攒了好多天的题……

题目大意：有n支NBA球队，这些队伍属于同一个半区，已知各队目前已经赢了几场以及还要打几场（赢了的场次和没打的场次不一定是和相同半区内的对手），另外已知一个n * n的矩阵，a[i][j]代表i和j还要打的比赛场数。根据这些条件，请问队伍1有没有获得半区冠军的可能性（若积分相同则均为冠军）

做法：完全没有头绪啊QAQ

首先考虑这样的条件：给出的n*n矩阵是两两比赛的数量，那么这两个队伍和彼此比赛时的赢的总数就等于矩阵对应位置的值。再想到：题目要求第一个队伍比其他队伍赢的场数都多，而对于每个队伍来说，赢的场数等于之前已经赢的场数加上之后赢的场数，之后赢的场数只有上限，而且需要有彼此比赛的两个队伍的比赛数量做限制，那么，图就出来啦

建图：

S ：0

比赛节点：1-tot（这里面只是矩阵不包括第1行+第一列，剩余部分的一半而且是>0的）

队伍节点：tot+1~tot+n-1

T：tot+n

源点向比赛节点连num[i][j]的容量（这些边求和得sum），比赛节点向对应两个队伍连num[i][j]容量，队伍向汇点连接w[1]+r[1]-w[i]容量。（这个边流量小于0也输出no）最大流>=sum成立

#include <stdio.h>
#include<cstring>
#include <iostream>
using namespace std;
const int oo=0x3f3f3f3f;
const int mm=900000;
const int mn=900000;
int node ,scr,dest,edge;
int ver[mm],flow[mm],Next[mm];
int head[mn],work[mn],dis[mn],q[mn];
void prepare(int _node,int _scr,int _dest)
{
    node=_node,scr=_scr,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++;
}
bool Dinic_bfs()
{
    int i,u,v,l,r=0;
    for(i=0; i<node; i++)
        dis[i]=-1;
    dis[q[r++]=scr]=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];
        while(delta=Dinic_dfs(scr,oo))
            ret+=delta;
    }
    return ret;
}
int n;
int w[30],r[30],num[30][30];
int main()
{
 //   freopen("cin.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)scanf("%d",&w[i]);
        for(int i=1;i<=n;i++)scanf("%d",&r[i]);
        int sum=0,tot=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&num[i][j]);
                if(i==1||j==1)continue;
                if(i<=j||num[i][j]==0)continue;
                tot++;
                sum+=num[i][j];
            }
        }
        prepare(1+tot+n,0,tot+n);
        int fir=0;
        bool flag=1;
        for(int i=1;i<=n&&flag;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==1||j==1)continue;
                if(i<=j||num[i][j]==0)continue;
                fir++;
                addedge(0,fir,num[i][j]);
                addedge(fir,i+tot-1,num[i][j]);
                addedge(fir,j+tot-1,num[i][j]);
            }
            if(i==1)continue;
            if(w[1]+r[1]-w[i]<0)flag=0;
            addedge(tot+i-1,tot+n,w[1]+r[1]-w[i]);
        }
        //printf("sum=%d,Dinic_flow=%d\n",sum,Dinic_flow());
        if(Dinic_flow()==sum&&flag)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}