题意：有n(<=20)只队伍比赛, 队伍i初始得分w[i], 剩余比赛场数r[i](包括与这n只队伍以外的队伍比赛), mat[i][j]表示队伍i与队伍j剩余比赛场数, 没有平局, 问队伍0有没有可能获得这n队中的第一名(可以有并列第一).
做法1：其实第一个队可以不用管它了,n支队我们将它压缩到n-1。
//球队编号[0,n-2]
//比赛数[n-1,n-2+id]
//超级源n-1+id
//超级汇n+id
//共n+id+1个点
把n-1只队伍作为顶点(把0号点去掉还剩n-1), 把(i<j)的所有场比赛作为顶点建图, 设i和j参加的比赛为c(i,j), 其数量为num(c(i,j)), 则i, j往c(i,j)连权值为num(c(i,j))的弧, c(i,j)往汇点也连权值为num(c(i,j))的弧, 超级源和每个队伍代表的顶点连流量是w[0]-w[i](w[0]是0号点赢得剩下所有比赛的得分),最大这样只要这条往汇点的弧满流, 则i, j赢的场数和一定为num(c(i,j)).
理解就是如果满流，那么所有的比赛可以安排，而且由于s->i已经控制了每个队可以赢得的比赛的上界，即使全部流到汇点也不会超过0号点的得分。
PS:我记得上次做了个浙大的题目，貌似和他很像，但是构图方法不一样，这题可以再研究下。
int mat[maxn][maxn];
int idx[maxn][maxn];
int n;
int w[maxn];
int r[maxn];
int s,t;
//球队编号[0,n-2]
//比赛数[n-1,n-2+id]
//超级源n-1+id
//超级汇n+id
//共n+id+1个点
//id中返回比赛数
int id;
int sum=0;
void input(int n)
{
id=0;
sum=0;
memset(idx,-1,sizeof(idx));
for(int i=0;i<n;i++)
scanf("%d",&w[i]);
for(int i=0;i<n;i++)
scanf("%d",&r[i]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&mat[i][j]);
//
/**//*
for(int i=1;i<n;i++)
w[0]+=mat[0][i];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
r[i]-=mat[i][j];
}
*/
w[0]+=r[0];
//剩下i对外区比赛场次
for(int i=1;i<n;i++)
for(int j=i+1;j<n;j++)
{
idx[i][j]=id++;
sum+=mat[i][j];
}
s=n-1+id;
t=n+id;
}
int main()
{
scanf("%d",&n);
input(n);
for(int i=0;i<n+id+1;i++)
adj[i]=NULL;
len=0;
//
for(int i=1;i<n;i++)
for(int j=i+1;j<n;j++)
{
insert(i-1,idx[i][j]+n-1,mat[i][j]);
insert(j-1,idx[i][j]+n-1,mat[i][j]);
insert(idx[i][j]+n-1,t,mat[i][j]);
}
for(int i=1;i<n;i++)
if(w[0]<w[i])
{
printf("NO\n");
return 0;
}
for(int i=1;i<n;i++)
insert(s,i-1,w[0]-w[i]);
if(sap(n+id+1,s,t)==sum)
printf("YES\n");
else
printf("NO\n");
return 0;
}做法二: 这个构图更为简单直观(不容易错)，不需要再建立比赛的节点，结点数O(n).
具体构图方法见
http://www.cppblog.com/abilitytao/archive/2010/07/21/120933.html
int mat[maxn][maxn];
int n;
int w[maxn];
int r[maxn];
int s,t;
//超级源0
//超级汇n
//共n+1个点
int sum;
void input(int n)
{
sum=0;
for(int i=0;i<n;i++)
scanf("%d",&w[i]);
for(int i=0;i<n;i++)
scanf("%d",&r[i]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&mat[i][j]);
w[0]+=r[0];
//剩下i对外区比赛场次
s=0;
t=n;
}
int main()
{
scanf("%d",&n);
input(n);
for(int i=0;i<n+1;i++)
adj[i]=NULL;
len=0;
//
int arr[maxn];
memset(arr,0,sizeof(arr));
for(int i=1;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
arr[i]+=mat[i][j];
sum+=mat[i][j];
}
insert(s,i,arr[i]);
}
for(int i=1;i<n;i++)
if(w[0]<w[i])
{
printf("NO\n");
return 0;
}
for(int i=1;i<n;i++)
insert(i,t,w[0]-w[i]);
for(int i=1;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
insert(i,j,mat[i][j]);
}
}
if(sap(t+1,s,t)==sum)
printf("YES\n");
else
printf("NO\n");
return 0;
}