学步园

       题意：现一个队有N个人，每个人已经赢了ai场，还有bi场比赛没打（可能不是跟本队的打，且比赛没有平局）。现给出N*N的矩阵g，g[i][j]表示i和j还有几场比赛要打(g[i][i]=0且g[i][j]=g[j][i])。问第一个人是否可能是整个队赢的最多的。

       分析：要第一个人赢的场数最多，那么第一个人剩下的场全部赢（也就确定了其它人最多赢的场数了），而其它人跟队外的人打的话一定要输。而对于g[i][j]来说，这么多场次肯定要人赢和输，我们考虑赢的情况。S连除第一个人，权值为第一个人赢的场数-已赢的场数，对于g[i][j]来说，i，j分别连场次，权值为g[i][j]；场次连T，权值为g[i][j]。求最大流，判断是否为总的场次。如果是，那么就可能，输出YES。

#include<stdio.h>
#include<iostream>
using namespace std;

const int maxn=440;
const int maxm=21000;
const int maxint=0x3fffffff;
struct edge
{
	int u,v,w,next;
}e[maxm];

int S,T,n,a[maxn],b[maxn],pre[maxn],dist[maxn],g[maxn][maxn],edgeNum,first[maxn];
void Addedge(int u,int v,int w)
{
	e[edgeNum].u=u,e[edgeNum].v=v,e[edgeNum].w=w,e[edgeNum].next=first[u],first[u]=edgeNum++;
	e[edgeNum].u=v,e[edgeNum].v=u,e[edgeNum].w=0,e[edgeNum].next=first[v],first[v]=edgeNum++;
}

bool Dinic_Label()
{
	int i,j,k,head=0,tail=0,q[maxn];
    memset(pre,-1,sizeof(pre));
    memset(dist,0,sizeof(dist));
	q[tail++]=S;
	dist[S]=1;

	while(head!=tail)
	{
		k=q[head];
		head=(head+1)%maxn;
		for(i=first[k];i!=-1;i=e[i].next)
		{
			j=e[i].v;
			if(e[i].w>0&&!dist[j])//注意这里有e[i].w>0
			{
				dist[j]=dist[k]+1;
				if(j==T) return true;
				q[tail]=j;
				tail=(tail+1)%maxn;
			}
		}
	}
	return false;
}
int Dinic_Augment(int s)
{
	int i,j,min,sum;
	if(s==T)
	{
		for(min=maxint,i=pre[T];i!=-1;i=pre[e[i].u])//注意i=pre[e[i].u]而不是i=pre[i]
			if(min>e[i].w)
				min=e[i].w;

		for(i=pre[T];i!=-1;i=pre[e[i].u])//
		{
			e[i].w-=min;
			e[i^1].w+=min;//是^，而不是+1,-1
		}
		return min;
	}

	for(sum=0,i=first[s];i!=-1;i=e[i].next)
	{
		j=e[i].v;
		if(e[i].w>0&&dist[s]+1==dist[j])//e[i].w>0和dist[s]+1==dist[j]缺一不可
		{
			pre[j]=i;
		    sum+=Dinic_Augment(j);
		}
	}
	return sum;
}
int Dinic()
{
	int sum=0;

	while(Dinic_Label())
		sum+=Dinic_Augment(S);
	return sum;
}
int main()
{
	int i,j,k,sum,sum1;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		for(i=0;i<n;i++)
			scanf("%d",&b[i]);
		k=a[0]+b[0];
		S=0,T=430;
		edgeNum=0;
		memset(first,-1,sizeof(first));
		for(sum=0,sum1=0,i=0;i<n;i++)
			for(j=0;j<n;j++)
			{
				scanf("%d",&g[i][j]);
				if(i&&i<j&&g[i][j])
				{
					Addedge(i,sum+n,g[i][j]);
					Addedge(j,sum+n,g[i][j]);
					Addedge(sum+n,T,g[i][j]);
					sum++;
					sum1+=g[i][j];
				}
			}
		for(i=1;i<n;i++)
		{
			if(k<a[i])
			{
				printf("NO\n");
				break;
			}
			else
				Addedge(S,i,k-a[i]);
		}
		if(i<n) continue;
		if(Dinic()==sum1) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}