題意：有n(<=20)只隊(duì)伍比賽, 隊(duì)伍i初始得分w[i], 剩余比賽場(chǎng)數(shù)r[i](包括與這n只隊(duì)伍以外的隊(duì)伍比賽), mat[i][j]表示隊(duì)伍i與隊(duì)伍j剩余比賽場(chǎng)數(shù), 沒有平局, 問隊(duì)伍0有沒有可能獲得這n隊(duì)中的第一名(可以有并列第一).
做法1：其實(shí)第一個(gè)隊(duì)可以不用管它了,n支隊(duì)我們將它壓縮到n-1。
//球隊(duì)編號(hào)[0,n-2]
//比賽數(shù)[n-1,n-2+id]
//超級(jí)源n-1+id
//超級(jí)匯n+id
//共n+id+1個(gè)點(diǎn)
把n-1只隊(duì)伍作為頂點(diǎn)(把0號(hào)點(diǎn)去掉還剩n-1), 把(i<j)的所有場(chǎng)比賽作為頂點(diǎn)建圖, 設(shè)i和j參加的比賽為c(i,j), 其數(shù)量為num(c(i,j)), 則i, j往c(i,j)連權(quán)值為num(c(i,j))的弧, c(i,j)往匯點(diǎn)也連權(quán)值為num(c(i,j))的弧, 超級(jí)源和每個(gè)隊(duì)伍代表的頂點(diǎn)連流量是w[0]-w[i](w[0]是0號(hào)點(diǎn)贏得剩下所有比賽的得分),最大這樣只要這條往匯點(diǎn)的弧滿流, 則i, j贏的場(chǎng)數(shù)和一定為num(c(i,j)).
理解就是如果滿流，那么所有的比賽可以安排，而且由于s->i已經(jīng)控制了每個(gè)隊(duì)可以贏得的比賽的上界，即使全部流到匯點(diǎn)也不會(huì)超過0號(hào)點(diǎn)的得分。
PS:我記得上次做了個(gè)浙大的題目，貌似和他很像，但是構(gòu)圖方法不一樣，這題可以再研究下。
int mat[maxn][maxn];
int idx[maxn][maxn];
int n;
int w[maxn];
int r[maxn];
int s,t;
//球隊(duì)編號(hào)[0,n-2]
//比賽數(shù)[n-1,n-2+id]
//超級(jí)源n-1+id
//超級(jí)匯n+id
//共n+id+1個(gè)點(diǎn)
//id中返回比賽數(shù)
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對(duì)外區(qū)比賽場(chǎng)次
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;
}做法二: 這個(gè)構(gòu)圖更為簡(jiǎn)單直觀(不容易錯(cuò))，不需要再建立比賽的節(jié)點(diǎn)，結(jié)點(diǎn)數(shù)O(n).
具體構(gòu)圖方法見
http://m.shnenglu.com/abilitytao/archive/2010/07/21/120933.html
int mat[maxn][maxn];
int n;
int w[maxn];
int r[maxn];
int s,t;
//超級(jí)源0
//超級(jí)匯n
//共n+1個(gè)點(diǎn)
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對(duì)外區(qū)比賽場(chǎng)次
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;
}