网络流经典模型之——竞赛问题SGU 326 Perspective

    停摆？？停摆你妹啊！！2011-2012NBA赛季开已经打啦！你OUT了。

    有n支队伍比赛，n<=20。已经打了一些比赛，并且知道了A赛区的队伍的目前得分。队伍i的目前得分为score[i]，剩余比赛场次为remain[i]，剩余场次包括同赛区和异赛区的比赛。用match[i][j]表示A区队伍的剩余的比赛情况，i和j剩余的比赛场数。当然，remain[i]>=sigma{match[i][k],1<=k<=n}。要知道，篮球比赛是没有平局的，问队伍1可不可能在赛季末获得A区的第一名(可以并列第一)？

    解：

    1. 显然，有种情况是：当队伍1赢下剩下所有比赛，其余队伍输掉剩余比赛，队伍1也不可能赢得第一。

    2. 增设源点s和汇点t，两类点：左边点代表队伍，右边点代表某两个队伍之间的比赛。

        s到第一类点连边，容量为那支队伍还可以赢得的最多的比赛场数，即（队伍1目前得分+队伍1的剩余比赛场数-队伍i的目前得分）；

        第二类点到t连边，容量为该点代表的两只队伍剩余的比赛场数K；

        第一类点到第二类点：若队伍i和队伍j之间有比赛，且对应的第二类点的标号为p，则连边(i,p,INF),(j,p,INF)。

    3. 求最大流。若第二类点到t的边都满流，就可以找到一组解，否则无解。

为何这样建图是对的呢？可以了解到建图的形式为S-->每个队-->比赛-->T，就是把剩余的比赛场数分配到每个队中，每个队的得分不能超过限制。当然这个限制还不够，还需要最小割全部切到与T相连的边上；否则，最小割肯定切到至少两个队伍上的边，而且要打的比赛>0，这样，本来这两个队的得分已经==队伍1的最高得分，再打比赛，肯定会有一个队超过限制，这样队伍1就不肯能获得冠军了。

     复杂度分析：点数最多有2+n+(n+1)*n/2<=232，显然用最大流是合适的。听说有更好的方法。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxv = 1000;
const int maxe = 10000;
int n;
int score[30];
int remain[30];
int match[30][30];
//
struct Edge
{
    int v;
    int next;
    int flow;
};
Edge e[maxe];
int head[maxv],edgeNum;
int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];

void addEdge(int a,int b,int c)
{
    e[edgeNum].v = b;
    e[edgeNum].flow = c;
    e[edgeNum].next = head[a];
    head[a] = edgeNum++;
    e[edgeNum].v = a;
    e[edgeNum].flow = 0;
    e[edgeNum].next = head[b];
    head[b] = edgeNum++;
}

void Init()
{
    edgeNum = 0;
    memset(head,-1,sizeof(head));
    memset(d,0,sizeof(d));
}

int sap(int s,int t,int n)       //源点，汇点，结点总数
{
    int i,x,y;
    int f,ans = 0;
    for(i = 0; i < n; i++)
        now[i] = head[i];
    vh[0] = n;
    x = s;
    while(d[s] < n)
    {
        for(i = now[x]; i != -1; i = e[i].next)
            if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x])
                break;
            if(i != -1)
            {
                now[x] = preh[y] = i;
                pre[y] = x;
                if((x=y) == t)
                {
                    for(f = INF,i=t; i != s; i = pre[i])
                        if(e[preh[i]].flow < f)
                            f = e[preh[i]].flow;
                    ans += f;
                    do
                    {
                        e[preh[x]].flow -= f;
                        e[preh[x]^1].flow += f;
                        x = pre[x];
                    }while(x!=s);
                }
            }
            else
            {
                if(!--vh[d[x]])
                    break;
                d[x] = n;
                for(i=now[x]=head[x]; i != -1; i = e[i].next)
                {
                    if(e[i].flow > 0 && d[x] > d[e[i].v] + 1)
                    {
                        now[x] = i;
                        d[x] = d[e[i].v] + 1;
                    }
                }
                ++vh[d[x]];
                if(x != s)
                    x = pre[x];
            }
    }
    return ans;
}
//

int main()
{
    int i,j,k;
    int cnt;
    while(scanf("%d",&n)!=EOF)
    {
        Init();
        cnt = 0;
        for(i = 1; i <= n; i++)
            scanf("%d",&score[i]);
        for(i = 1; i <= n; i++)
            scanf("%d",&remain[i]);
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                scanf("%d",&match[i][j]);
        int high = score[1] + remain[1];
        for(i = 2; i <= n; i++)      //剪枝：1队剩下比赛全赢并且其余队全输，仍不能赢得比赛。
        {
            if(score[i] > high)
                break;
        }
        if(i<=n)
        {
            printf("NO\n");
            continue;
        }
        for(i = 2; i <= n; i++)
            for(j = i+1; j <= n; j++)
                if(match[i][j])
                    cnt++;
        int source = 0;
        int sink = cnt+n+1;
        int flow = 0;
        for(i = 2; i <= n; i++)
            addEdge(source,i,high-score[i]);
        k = 0;
        for(i = 2; i <= n; i++)
        {
            for(j = i+1; j <= n; j++)
            {
                if(match[i][j])
                {
                    ++k;
                    addEdge(i,n+k,INF);
                    addEdge(j,n+k,INF);
                    addEdge(n+k,sink,match[i][j]);
                    flow += match[i][j];
                }
            }
        }
        if(flow == sap(source,sink,sink+1))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}