sgu 326 Perspective(最大ストリーム)

同じ試合区を知っているNチームは、現在得点があることを知っていて、残りの試合場数(本試合区内のものと、試合区をまたぐものを含む)、試合区内部の対戦表を知っていて、1番チームが試合区のチャンピオンを獲得できるかどうかを聞いています(並列できます).
大神の建図、私はもう一度繰り返して、理解を深めます:
まず、私たちは1番チームの残りの試合を選んですべて勝って、残りのチームは試合区をまたいですべて負けました.もしそうなら、1番を超えたチームがあるなら、判断するまでもなく「NO」になる.
もし1番のチームに芝居があったら、私たちは図を作り始めます.
源点から残りのチームの側(1番チームは構わない)までつながっており、そのチームと1番チームの勝敗差がある.
チームIとチームJの間に試合がある場合は、ポイントPを1つ加え、3つの辺I->P、J->P、P->送金ポイントまで、権値はチームIとチームJの間の残りの試合数、すなわちmat[i][j]である.
次に、最大ストリームが、集約点に接続されたすべてのエッジの重み値和に等しいかどうかを判断し、等しいのが「YES」である.
証明:ソースポイントが発行するエッジのエッジ権は実質的に臨界線であり、これらのエッジが満流であれば、これらのエッジが接続されているチームと1番チームの勝場数が等しいことを意味する.ポイントの辺権は残りの試合場数を表しており、もし彼らが満流であれば、試合が終わったことを意味している.明らかに、ポイントの不満の流れは、少なくとも1組のチーム(対戦関係のある2つのチーム)の得点が1番のチームと等しいことを示しており、試合が終わっていない場合は、その2つのチームが誰が負けても勝っても、勝者の得点は必ず1番のチームを超えている.
コード:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define find_min(a,b) a<b?a:b
#define MAX 0x3f3f3f3f
using namespace std;

const int N = 30;
const int NN = 1000;
const int M = 30000;

struct Edge{
	int s,e,v,next;
}edge[M];

int e_num,sum,head[NN],d[NN],sp,tp;
int n,score[N],remain[N],mat[N][N];

void AddEdge(int a,int b,int c){
	edge[e_num].s=a; edge[e_num].e=b; edge[e_num].v=c;
	edge[e_num].next=head[a]; head[a]=e_num++;

	edge[e_num].s=b; edge[e_num].e=a; edge[e_num].v=0;
	edge[e_num].next=head[b]; head[b]=e_num++;
}

int bfs(){
	queue <int> q;
	memset(d,-1,sizeof(d));
	d[sp]=0;
	q.push(sp);
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		for(int i=head[cur];i!=-1;i=edge[i].next){
			int u=edge[i].e;
			if(d[u]==-1 && edge[i].v>0){//    ,      0
				d[u]=d[cur]+1;
				q.push(u);
			}
		}
	}
	return d[tp] != -1;//        ,           
}

int dfs(int a,int b){//a   
	int r=0;
	if(a==tp)return b;
	for(int i=head[a];i!=-1 && r<b;i=edge[i].next){
		int u=edge[i].e;
		if(edge[i].v>0 && d[u]==d[a]+1){
			int x=find_min(edge[i].v,b-r);
			x=dfs(u,x);
			r+=x;
			edge[i].v-=x;
			edge[i^1].v+=x;
		}
	}
	if(!r)d[a]=-2;
	return r;
}

void dinic(int sp,int tp){
	int total=0,t;
	while(bfs()){
		while(t=dfs(sp,MAX))
		total+=t;
	}
	if(sum==total)puts("YES");
	else puts("NO");
}

int main()
{
	int i,j;
	while(~scanf("%d",&n))
	{
		memset(score,0,sizeof(score));
		memset(mat,0,sizeof(mat));
		memset(remain,0,sizeof(remain));
		for(i=1;i<=n;i++)
			scanf("%d",&score[i]);
		for(i=1;i<=n;i++)
			scanf("%d",&remain[i]);

		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++)scanf("%d",&mat[i][j]);
		}

		score[1]+=remain[1];
		int flag=1;
		for(i=2;i<=n;i++){
			if(score[i]>score[1]){
				flag=0;break;
			}
		}
		if(!flag){
			puts("NO");continue;
		}

		int m=n;
		int id[N][N];
		for(i=2;i<=n;i++){
			for(j=i+1;j<=n;j++)if(mat[i][j]>0)id[i][j]=++m;
		}


		sum=0; e_num=0;
		memset(head,-1,sizeof(head));

		sp=1; tp=m+1;

		for(i=2;i<=n;i++){
			for(j=i+1;j<=n;j++){
				if(mat[i][j]>0){
					sum+=mat[i][j];
					AddEdge(i,id[i][j],mat[i][j]);
					AddEdge(j,id[i][j],mat[i][j]);
					AddEdge(id[i][j],tp,mat[i][j]);
				}
			}
		}
		for(i=2;i<=n;i++)
			AddEdge(sp,i,score[1]-score[i]);

		dinic(sp,tp);
	}
	return 0;
}