题目传送门：http://acm.whu.edu.cn/olive/problem/124
【题目大意】
给你N支球队，M场比赛，每个球队开始时都有初始的分数，现问你能否通过安排一下剩余M场比赛的结果，使第N支球队最后的分数最高。
【输入格式】
输入包含多组数据。每组数据先给两个数N,M，然后接下来一行有N个数，表示当前球队的分数，接下来M行，每行两个整数A,B表示A,B之间有一场比赛，比赛规则：赢的球队得两分，平局各得一分，输的球队得0分。
【输出格式】
如果可以使第N支球队分数最高，输出“YES”，否则输出"NO"。
【样例输入】
5 8
2 1 0 0 1
1 2
3 4
2 3
4 5
3 1
2 4
1 4
3 5
5 4
4 4 1 0 3
1 3
2 3
3 4
4 5
【样例输出】
YES
NO
【备注】
N<=100，M<=1000
PS（题目原话）：The problem is so hard that even I have told you the method here is "maximum network flow", you can't solve it. You can have a try, but don?t waste too much time here if you are not perfect at modeling a network.（就是我给你说这是道网络流的题你都做不起（真皮））
【题目分析】
既然人家诚心诚意的给你说了用网络流做，那我们就老老实实的用网络流吧。。。
第一点还是很明显的，对于所有有N的比赛，我们都让N赢，这样N就有了一个最大分数。
然后剩下的比赛，我们发现不管有输有赢还是平局，两队总共得到2分，这就变成了一个分配问题，限制一下每个球队的匹配上限，然后看一下分配的分数能否分完就行了，能分完就输出YES，否则就输出NO。
【代码~】
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+10;
const int MAXM=1e5+10;
const int INF=0x3f3f3f3f;
int n,m,s,t,cnt;
int head[MAXN],cur[MAXN],depth[MAXN];
int nxt[MAXM],to[MAXM],w[MAXM];
queue<int> q;
bool bfs()
{
while(!q.empty())
q.pop();
memset(depth,0,sizeof(depth));
depth[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(w[i]&&depth[v]==0)
{
depth[v]=depth[u]+1;
q.push(v);
}
}
}
if(depth[t]==0)
return false;
return true;
}
int dfs(int u,int dist)
{
if(u==t)
return dist;
for(int &i=cur[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(w[i]&&depth[v]==depth[u]+1)
{
int di=dfs(v,min(dist,w[i]));
if(di>0)
{
w[i]-=di;
w[i^1]+=di;
return di;
}
}
}
return 0;
}
int dinic()
{
int ans=0;
while(bfs())
{
for(int i=s;i<=t;++i)
cur[i]=head[i];
while(int d=dfs(s,INF))
ans+=d;
}
return ans;
}
void Add(int x,int y,int z)
{
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
w[cnt]=z;
cnt++;
}
void add(int x,int y,int z)
{
Add(x,y,z);
Add(y,x,0);
}
int score[MAXN];
int tot;
int main()
{
while(~scanf("%d%d",&n,&m))
{
tot=0;
memset(head,-1,sizeof(head));
s=0,t=n+m+1;
for(int i=1;i<=n;++i)
scanf("%d",&score[i]);
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
if(max(x,y)==n)
score[n]+=2;
else
{
tot+=2;
add(s,i,2);
add(i,x+m,2);
add(i,y+m,2);
}
}
bool flag=true;
for(int i=1;i<n;++i)
{
if(score[i]>=score[n]-1)
{
flag=false;
break;
}
add(i+m,t,score[n]-score[i]-1);
}
if(flag&&dinic()==tot)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
