SGU326_Perspective

NBA打比赛。所有的比赛被分为多个团队。有的比赛是团内的，有的是与团外的队伍打的。

给出团内每个队伍已得分，以及总共有多少场比赛，还有团内所有队伍之间有多少场比赛？

问1队是否可能是分数最高的一个队伍。（题目没说是否唯一最高，枚举题意得知不是唯一）

又是一个竞赛图的最大流。团内的比赛，如果有一个队伍是1队，那么安排结果1队胜利，另一队伍失败。

对于所有与外团的比赛，与1队有关的都胜利，否则失败。

接下来建图，我们做完前面的工作后，分别统计所有的队伍得分，1队分数减去x队的分数就是x队在所有的团内赛中最多能够胜利的场数。

模型就出来了，源点->队伍->比赛->汇点，最终我们只要判断所有比赛的出边是否满流，即所有的比赛能否安排得下即可。

召唤代码君：

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 5550
#define maxm 55550
using namespace std;

int next[maxm],to[maxm],c[maxm],first[maxn],edge=-1;
int score[maxn],test[maxn],tag[maxn],TAG=520;
bool can[maxn];
int a[222][222],node=-1,d[maxn];
int Q[maxn],bot,top;
int alltest=0,ans,n,m,s,t;

int addnode()
{
    first[++node]=-1;
    return node;
}

void addedge(int U,int V,int W)
{
    edge++;
    to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge;
    edge++;
    to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge;
}

bool bfs()
{
    Q[bot=top=1]=t,d[t]=0,tag[t]=++TAG,can[t]=false;
    while (bot<=top)
    {
        int cur=Q[bot++];
        for (int i=first[cur]; i!=-1; i=next[i])
            if (c[i^1]>0 && tag[to[i]]!=TAG)
            {
                tag[to[i]]=TAG,can[to[i]]=false;
                d[to[i]]=d[cur]+1,Q[++top]=to[i];
                if (to[i]==s) return true;
            }
    }
    return false;
}

int dfs(int cur,int num)
{
    if (cur==t) return num;
    int tmp=num,k;
    for (int i=first[cur]; i!=-1; i=next[i])
        if (c[i]>0 && tag[to[i]]==TAG && !can[to[i]] && d[to[i]]==d[cur]-1)
        {
            k=dfs(to[i],min(num,c[i]));
            if (k) num-=k,c[i]-=k,c[i^1]+=k;
            if (num==0) break;
        }
    if (num) can[cur]=true;
    return tmp-num;
}

bool _input()
{
    scanf("%d",&n);
    s=addnode();
    for (int i=1; i<=n; i++) t=addnode();
    t=addnode();
    for (int i=1; i<=n; i++) scanf("%d",&score[i]);
    for (int i=1; i<=n; i++) scanf("%d",&test[i]);
    for (int i=1; i<=n; i++) 
        for (int j=1; j<=n; j++) 
        {
            scanf("%d",&a[i][j]);
            if (!a[i][j] || i>=j) continue;
            test[i]-=a[i][j],test[j]-=a[i][j];
            if (i==1) score[1]+=a[i][j];
                else 
                {
                    alltest+=a[i][j];
                    int tmp=addnode();
                    addedge(i,tmp,a[i][j]);
                    addedge(j,tmp,a[i][j]);
                    addedge(tmp,t,a[i][j]);
                }
        }
    score[1]+=test[1];
    for (int i=2; i<=n; i++) 
    {
        if (score[i]>score[1]) return false;
        addedge(s,i,score[1]-score[i]);
    }
    int ans=0;
    while (bfs()) ans+=dfs(s,maxn);
    return ans==alltest;
}

int main()
{
    if (_input()) puts("YES");
        else puts("NO");
    return 0;
}