竞赛问题升级版——ZOJ3348

??? 在上一篇中已经介绍了一种利用网络流求解竞赛问题的解法，构图共有n^2个点。但当比赛队伍逐渐增大时，比如n=60，就会有3600个点，采用网络流显然效率不高。这里再介绍一种更简单的建模方式。

??? 解：

??? 1. 还是假设DD赢下剩下的所有比赛，最高得分为high。

??? 2. 对于剩下的比赛，随意定胜负。记录每位选手的得分score[i]，用champ[i][j]表示i赢j的次数。

??? 3. 增设源点和汇点，三类边：

?????? 边(s,i,score[i])，表示选手i有score[i]次胜利(比赛)要分配。

?????? 边(i,sink,high-1)，表示选手i最多的胜利场数不能超过DD。

?????? 边(i,j,champ[i][j])。这是最关键的，也是前面为什么可以任意定胜负。若从s流到点i的流量流到t，说明选手i赢了比赛；若流到j，表示该场胜利被j夺走，即j赢得比赛，所以上面说的假设仅仅是假设。

??? 4. 判断与s相连的边是否满流，若否则无解。

?? 复杂度：仅有n+2个点。

#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <string>using namespace std;const int INF = 0x7fffffff;const int maxv = 60;const int maxe = 15000;int score[55];int champ[55][55];//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;    int n,m;    int p;    int k;    int seq1,seq2;    char p1[15],p2[15],result[10];    map<string,int> mp;    map<string,int>::iterator it;    while(scanf("%d %d",&n,&m)!=EOF)    {        k = 0;        Init();        mp.clear();        memset(score,0,sizeof(score));        memset(champ,0,sizeof(champ));        mp["DD"] = 0;        for(i = 0; i < m; i++)        {            scanf("%s %s %s",p1,p2,result);            it = mp.find(p1);            if(it == mp.end())            {                seq1 = ++k;                mp[p1] = seq1;            }            else                seq1 = it->second;            it = mp.find(p2);            if(it == mp.end())            {                seq2 = ++k;                mp[p2] = seq2;            }            else                seq2 = it->second;            if(result[0] == 'w')                score[seq1]++;            else                score[seq2]++;        }        scanf("%d",&p);        for(i = 0; i < p; i++)        {            scanf("%s %s",p1,p2);            it = mp.find(p1);            if(it == mp.end())            {                seq1 = ++k;                mp[p1] = seq1;            }            else                seq1 = it->second;            it = mp.find(p2);            if(it == mp.end())            {                seq2 = ++k;                mp[p2] = seq2;            }            else                seq2 = it->second;            //假设序号小的赢得比赛            if(seq1 > seq2)                swap(seq1,seq2);            score[seq1]++;            champ[seq1][seq2]++;        }        it = mp.find("DD");        if(it == mp.end())        {            if(n == 1)                printf("Yes\n");            else                printf("No\n");            continue;        }        int source = 0;        int sink = k+1;        int sum = 0;        for(i = 1; i <= k; i++)        {            sum += score[i];            addEdge(source,i,score[i]);            addEdge(i,sink,score[0]-1);            for(j = i+1; j <= k; j++)            {                if(champ[i][j])                    addEdge(i,j,champ[i][j]);            }        }        if(sum == sap(source,sink,sink+1))            printf("Yes\n");        else            printf("No\n");    }    return 0;}

?

?

?