WHU 1124 Football Coach(최대 흐름)

Problem 1124 - Football Coach
Time Limit: 2000MS   
Memory Limit: 65536KB   
Difficulty: 1 
Total Submit: 82  
Accepted: 46  
Special Judge: No
Description
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. 
Input
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.
Output
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.
Sample Input
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
Sample Output
YES
NO
Hint
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.
Source
2006 Team Select Round 3
제목:http://acm.whu.edu.cn/learn/problem/detail?problem_id=1124
분석: 이 문제는 직접적으로 가장 큰 흐름이라고 말하고 직접==
우선 욕심을 내서 팀 N과 겨루는 경기에 대해 팀 N승으로 2점을 더하면 팀 N의 최고 성적을 limit로 기록한다
일반적인 경기에 대해 구성이 시작되었다. 매 경기와 매 팀을 점으로 보고 원점과 환점을 증가한다. 원점과 매 경기의 연결 용량이 2인 변(경기당 최대 2점을 준다), 매 경기와 그의 두 참가팀은 용량이 2인 변(이렇게 세 가지 결말의 분배를 충족시킨다)을 연결한다. 그리고 각 팀과 환점에 대해 직접적으로 이 팀의 원래 점수가 limit-1보다 크면 이해할 수 없다.그렇지 않으면 용량이 (limit-1-원래 분수) 인 모서리를 연결합니다.
만약 최대 만류가 있으면 해가 있는 것이고, 그렇지 않으면 해가 없는 것이다
코드:

#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],score[mn];
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,u,v,m,n,sum;
    while(scanf("%d%d",&n,&m)!=-1)
    {
        for(i=1;i<=n;++i)scanf("%d",&score[i]);
        prepare(n+m+2,0,n+m+1);
        sum=0;
        for(i=1;i<=m;++i)
        {
            scanf("%d%d",&u,&v);
            if(u==n||v==n)score[n]+=2;
            else
            {
                sum+=2;
                addedge(src,i,2);
                addedge(i,m+u,2);
                addedge(i,m+v,2);
            }
        }
        for(i=1;i<n;++i)
        {
            if(score[i]>=score[n]-1)break;
            addedge(m+i,dest,score[n]-1-score[i]);
        }
        if(i==n&&Dinic_flow()==sum)puts("YES");
        else puts("NO");
    }
    return 0;
}