竞赛问题升级版——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;}?
?
?