记录编号	10045	评测结果	AAAAAAAAAA
题目名称	K- 联赛	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2009-04-24 15:22:33	内存使用	1.66 MiB

/* 
 * Problem: HAOI2009 模拟4 kleague
 * Author: Guo Jiabao
 * Time: 2009.4.24 15:21
 * State: Solved
 * Memo: 网络流
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=25*25,MAXM=MAXN*8,INF=0x7FFFFFFF;
using namespace std;
struct edge
{
	edge *next,*op;
	int t,c;
}ES[MAXM],*V[MAXN],*P[MAXN],*Stae[MAXN];
int Win[MAXN],TWin[MAXN],Match[MAXN][MAXN];
int Lv[MAXN],Stap[MAXN];
int N,S,T,EC;
bool Dinic_BFS()
{
	int u,v,head=0,tail=-1;
	memset(Lv,-1,sizeof(Lv));
	Lv[Stap[++tail]=S]=0;
	while (head<=tail)
	{
		u=Stap[head++];
		for (edge *k=V[u];k;k=k->next)
		{
			v=k->t;
			if (k->c && Lv[v]==-1)
			{
				Lv[v]=Lv[u]+1;
				Stap[++tail]=v;
				if (v==T)
					return true;
			}
		}
	}
	return false;
}
int Dinic_Augment()
{
	int u,v,delta,Stop,Flow=0;
	for (u=S;u<=T;u++)
		P[u]=V[u];
	Stap[Stop=1]=S;
	while (Stop)
	{
		u=Stap[Stop];
		if (u!=T)
		{
			for (;P[u];P[u]=P[u]->next)
			{
				if (P[u]->c && Lv[v=P[u]->t]==Lv[u]+1)
					break;
			}
			if (P[u])
			{
				Stap[++Stop]=v;
				Stae[Stop]=P[u];
			}
			else
			{
				Stop--;
				Lv[u]=-1;
			}
		}
		else
		{
			delta=INF;
			for (u=Stop;u>=2;u--)
				if (Stae[u]->c < delta)
					delta=Stae[u]->c;
			for (u=Stop;u>=2;u--)
			{
				Stae[u]->c -= delta;
				Stae[u]->op->c += delta;
				if (Stae[u]->c==0)
					v=u-1;
			}
			Flow+=delta;
			Stop=v;
		}
	}
	return Flow;
}
int Dinic()
{
	int Maxflow=0;
	while(Dinic_BFS())
		Maxflow += Dinic_Augment();
	return Maxflow;
}
void init()
{
	int i,j;
	freopen("kleague.in","r",stdin);
	freopen("kleague.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
		scanf("%d%d",&TWin[i],&S);
	for (i=1;i<=N;i++)
		for (j=1;j<=N;j++)
			scanf("%d",&Match[i][j]);
}
inline void addedge(int a,int b,int c)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
	ES[++EC].next=V[b];
	V[b]=ES+EC; V[b]->t=a; V[b]->c=0;
	V[a]->op=V[b]; V[b]->op=V[a];
}
void solve()
{
	int i,j,k,M,A,MaxFlow;
	for (i=1;i<=N;i++)
	{
		M=EC=S=A=0;
		T=N + N*(N-1)/2 + 1;
		memset(V,0,sizeof(V));
		for (j=1;j<=N;j++)
			Win[j]=TWin[j];
		for (j=1;j<=N;j++)
			Win[i] += Match[i][j];
		for (j=1;j<=N;j++)
		{
			if (i==j) continue;
			if (Win[i] - Win[j] < 0)
				break;
			addedge(S,j,Win[i] - Win[j]);
			for (k=j+1;k<=N;k++)
			{
				if (i==k) continue;
				++M;
				addedge(j,M+N,Match[j][k]);
				addedge(k,M+N,Match[j][k]);
				addedge(M+N,T,Match[j][k]);
				A+=Match[j][k];
			}
		}
		if (j<=N) continue;
		MaxFlow=Dinic();
		if (MaxFlow == A)
			printf("%d ",i);
	}
}
int main()
{
	init();
	solve();
	return 0;
}