WOJ1124-Football Coach

It is not an easy job to be a coach of a football team. The season is almost over, only a few matches are left to play. All of sudden the team 
manager comes to you and tells you bad news: the main sponsor of your club is not happy with your results and decided to stop sponsoring your 
team, which probably means the end of your club. The sponsor's decision is final and there is no way to change it unless... unless your team 
miraculously wins the league. 
The manager left you in deep thought. If you increase the number of practices and offer players a generous bonus for each match, you may be 
able to win all the remaining matches. Is that enough? You also have to make sure that teams with many points lose against teams with few 
points so that in the end, your team will have more points than any other team. You know some of the referees and can bribe them to manipulate 
the result of each match. But first you need to figure out how to manipulate the results and whether it is possible at all. 
There are N teams numbered 1 through N, your team has the number N. The current number of points of each team and the list of remaining 
matches are given. Your task is to find out whether it is possible to manipulate each remaining match so that the team N will finish with 
strictly more points than any other team. If it is possible, output "YES", otherwise, output "NO". In every match, the winning team gets 2 
points, the losing team gets 0. If the match ends with a draw, both teams get 1 point. 

输入格式

There will be multiple test cases. Each test case has the following form: The first line contains two numbers N(1 <= N <= 100) and M(0 <= M <=
1000). The next line contains N numbers separated by spaces giving the current number of points of teams 1, 2, ..., N respectively. The
following M lines describe the remaining matches. Each line corresponds to one match and contains two numbers a and b (a not equal to b, 1 <=
a,b <= N) identifying the teams that will play in the given match. There is a blank line after each test case.

输出格式

For each test case, output "YES" or "NO" to denote whether it's possible to manipulate the remaining matches so that the team N would win
the league.

样例输入

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

源点和每场比赛连一条流量为2的边，每场比赛和参加这场比赛的人连一条流量为2的边，每个人还有多少分才到第n个人的分数就对这个人到汇点连一条流量为这个差值的边，最后看源点所有边是否都满流就可以了。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 2000;//点数的最大值
const int MAXM = 200000;//边数的最大值
const int INF = 0x3f3f3f3f;
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];//注意是MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
void init(){
    tol = 0;
    memset(head,-1,sizeof(head));
}
//加边，单向图三个参数，双向图四个参数
void addedge(int u,int v,int w,int rw=0){
    edge[tol].to = v;edge[tol].cap = w;edge[tol].next = head[u];
    edge[tol].flow = 0;head[u] = tol++;
    edge[tol].to = u;edge[tol].cap = rw;edge[tol].next = head[v];
    edge[tol].flow = 0;head[v]=tol++;
}
int sap(int start,int end,int N){
    memset(gap,0,sizeof(gap));
    memset(dep,0,sizeof(dep));
    memcpy(cur,head,sizeof(head));
    int u = start;
    pre[u] = -1;
    gap[0] = N;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            for(int i = pre[u];i != -1; i = pre[edge[i^1].to])
                if(Min > edge[i].cap - edge[i].flow)
                        Min = edge[i].cap - edge[i].flow;
            for(int i = pre[u];i != -1; i = pre[edge[i^1].to]){
                edge[i].flow += Min;
                edge[i^1].flow -= Min;
            }
            u = start;
            ans += Min;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1;i = edge[i].next){
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = pre[v] = i;
                break;
            }
        }
        if(flag){
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1;i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min+1;
        gap[dep[u]]++;
        if(u != start) u = edge[pre[u]^1].to;
    }
    return ans;
}
int score[MAXN], from[MAXN], to[MAXN];
main() {
    int n, m;
    while(~scanf("%d %d", &n, &m)){
        int maxn = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &score[i]);
            if(i != n) maxn = max(maxn, score[i]);
        }
        int cnt = 0;
        for(int i = 0; i < m; i++){
            int u, v;
            scanf("%d %d", &u, &v);
            if(u == n || v == n) score[n] += 2;
            else from[++cnt] = u, to[cnt] = v;
        }
        if(score[n] < maxn) {
            puts("NO");
            continue;
        }
        int src = 0, sink = n + cnt + 1;
        init();
        for(int i = 1; i <= cnt; i++) addedge(src, n + i, 2);
        for(int i = 1; i < n; i++) addedge(i, sink, score[n] - 1 - score[i]);
        for(int i = 1; i <= cnt; i++){
            int u = from[i], v = to[i];
            addedge(n + i, u, 2);
            addedge(n + i, v, 2);
        }
        int maxflow = sap(src, sink, sink + 1);
        if(maxflow == cnt * 2) puts("YES");
        else puts("NO");
    }
}