记录编号	10054	评测结果	AAAAAAAAAA
题目名称	K- 联赛	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.697 s
提交时间	2009-04-24 21:12:43	内存使用	0.38 MiB

#include <iostream>

#define MAXN 30
#define MAXV 10000
#define INF 999999999

struct Match{
	int a,b,winner;
};

int n,m,win[MAXN],lose[MAXN],data[MAXN][MAXN];
int rem[MAXN];
struct Match match[MAXV];



bool check(int w,int maxwin)
{
	const int repeatTime=60000;
	int k,i,a,b,max;
	srand(w);
	for (i=1;i<=m;i++)
	{
		k=rand()%2;
		if (match[i].a==w)
			k=0;
		if (match[i].b==w)
			k=1;
		if (k==0)
		{
			match[i].winner=0;
			win[match[i].a]++;
		}
		else
		{
			match[i].winner=1;
			win[match[i].b]++;
		}
	}
	for (k=1;k<=repeatTime;k++)
	{
		i=rand()%m+1;
		if (match[i].a==w || match[i].b==w)
			continue;
		a=match[i].a;
		b=match[i].b;
		if (match[i].winner==0)
		{
			if (win[a]>win[b])
			{
				win[a]--;
				win[b]++;
				match[i].winner=1;
			}
		}
		else//winner is 1
			if (win[b]>win[a])
			{
				win[b]--;
				win[a]++;
				match[i].winner=0;
			}
	}
	max=0;
	for (i=1;i<=n;i++)
		if (win[i]>max)
			max=win[i];
	if (max<=maxwin)
		return true;
	return false;
}

void run()
{
	int w,i,maxwin=0;
	for (i=1;i<=n;i++)
		rem[i]=win[i];
	for (w=1;w<=n;w++)//get the WINING TEAM
	{
		for (i=1;i<=n;i++)
			win[i]=rem[i];
		maxwin=win[w];
		for (i=1;i<=n;i++)
			maxwin+=data[w][i];
		if (check(w,maxwin))
			printf("%d ",w);		
	}
}


void ini()
{
	int i,j,k;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d%d",&win[i],&lose[i]);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			scanf("%d",&data[i][j]);
	m=0;
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
		{
			for (k=1;k<=data[i][j];k++)
			{
				m++;
				match[m].a=i;
				match[m].b=j;
			}
		}

}

int main()
{
	freopen("kleague.in","r",stdin);
	freopen("kleague.out","w",stdout);
	ini();
	run();
	return 0;
}