记录编号	17057	评测结果	AAAAAAAAAA
题目名称	K- 联赛	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2010-07-06 15:25:29	内存使用	0.74 MiB

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>

using namespace std;
const int oo=200000000;

int w[40],yw[40],n,kmax,pn;
int a[40][40],ya[40][40];int lose[40][40];

struct edge
{
	int t,c;
	edge *op,*next;
}E[30000],*V[100];
int eh,S,T;

inline void addedge(int a,int b,int c)
{
	E[++eh].next=V[a];  V[a]=E+eh;  V[a]->t=b;  V[a]->c=c;
	E[++eh].next=V[b];  V[b]=E+eh;  V[b]->t=a;  V[b]->c=0;
	V[a]->op=V[b];  V[b]->op=V[a];
}

void init()
{
	scanf("%d",&n);
	int t;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&yw[i],&t);
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
	{
		scanf("%d",&ya[i][j]);
	}
}

void tanxin(int now)
{
	for (int i=1;i<=n;i++)
	{
		w[now]+=a[now][i];
		a[now][i]=0;
		a[i][now]=0;
	}

	for (int T=n;T>=1;T--)
	{
		int mini=T;
		for (int i=1;i<=n;i++)
		if (i!=now)
		{
				w[mini]+=a[mini][i];
				lose[i][mini]+=a[mini][i];
				a[mini][i]=0;
				a[i][mini]=0;
		}
	}
}

int d[100],vd[100];

int dfs(int u,int flow)
{
	int now=0;
	if (u==T) return flow;
	for (edge *e=V[u];e;e=e->next)
	if (e->c>0 && d[u]==d[e->t]+1)
	{
		int t=dfs(e->t,min(flow-now,e->c));
		if (t)
		{
			e->c-=t;
			now+=t;
			e->op->c+=t;
			if (now==flow) return now;
		}
	}
	if (d[S]>=pn) return now;
	if (--vd[d[u]]==0) d[S]=pn;
	vd[++d[u]]++;
	return now;
}

bool tiaozheng(int now)
{
	int need=0,ans=0;
	eh=0;
	memset(V,0,sizeof(V));
	S=0;T=66;
	for (int i=1;i<=n;i++)
	{
		if (w[i]>w[now])
		{
			need+=w[i]-w[now];
			addedge(i,T,w[i]-w[now]);
		}
		if (w[i]<w[now])
		{
			addedge(S,i,w[now]-w[i]);
		}
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
	if (lose[i][j])
	{
		addedge(i,j,lose[i][j]);
	}
	pn=n+2;
	vd[0]=pn;
	memset(d,0,sizeof(d));
	while (d[S]<pn)
	{
		ans+=dfs(S,oo);
	}
	if (ans==need) return true;
	return false;
}

int ans[100],ansh;

void solve()
{
	for (int i=1;i<=n;i++)
	{
		memcpy(w,yw,sizeof(yw));
		memcpy(a,ya,sizeof(ya));
		memset(lose,0,sizeof(lose));
		tanxin(i);
		if (tiaozheng(i)) ans[++ansh]=i;
	}
	for (int i=1;i<ansh;i++)
	{
		printf("%d ",ans[i]);
	}
	printf("%d\n",ans[ansh]);
}

int main()
{
	freopen("kleague.in","r",stdin);
	freopen("kleague.out","w",stdout);
	init();
	solve();
}