记录编号	363480	评测结果	AAAAAAAAAA
题目名称	K- 联赛	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-01-11 17:09:27	内存使用	5.49 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define ll long long 
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
const int maxn=1010;
const int inf=0x3f3f3f3f;
struct edge{
	int to,next,cap;
	edge(){}
	edge(int a,int b,int c){
		to=a,next=b,cap=c;
	}
}e[maxn*110];
int tot=1,head[maxn],cur[maxn];
void add(int u,int v,int w){
	e[++tot]=edge(v,head[u],w);head[u]=tot;
	e[++tot]=edge(u,head[v],0);head[v]=tot;
}
int S,T,n,dis[maxn],c[maxn][maxn],w[maxn];
queue<int>q;
int f(int i,int j){return (i-1)*n+j;}
bool bfs(){
	memset(dis,-1,sizeof dis);
	q.push(S),dis[S]=0;
	while(!q.empty()){
		int s=q.front();q.pop();
		for(int i=head[s];i;i=e[i].next){
			int to=e[i].to;
			if(e[i].cap&&dis[to]==-1)
				q.push(to),dis[to]=dis[s]+1;
		}
	}return dis[T]!=-1;
}
int dfs(int u,int flow){
	if(u==T) return flow;
	int cnt=0;
	for(int &i=cur[u];i;i=e[i].next){
		int to=e[i].to;
		if(e[i].cap&&dis[to]==dis[u]+1){
			int dd=dfs(to,min(e[i].cap,flow));
			e[i].cap-=dd,e[i^1].cap+=dd;
			flow-=dd,cnt+=dd;
			if(!flow) break;
		}
	}return cnt;
}
int dinic(){
	int cnt=0;
	while(bfs()){
		memcpy(cur,head,sizeof cur);
		cnt+=dfs(S,inf);
	}return cnt;
}
  
bool check(int x){
	memset(head,0,sizeof head);tot=1;int cnt=0;
	for(int i=1;i<=n;i++)cnt+=c[x][i];
	for(int i=1;i<=n;i++)if(w[x]+cnt<w[i]) return 0;
	S=n*n+n+1,T=S+1;
	for(int i=1;i<=n;i++){
		if(i==x) continue;
		add(i,T,w[x]+cnt-w[i]);
	}
	for(int i=1;i<=n;i++){
		if(i==x) continue;
		for(int j=1;j<i;j++){
			if(i==j ||j==x|| c[i][j]==0) continue;
			add(S,f(i,j)+n,c[i][j]);
			add(f(i,j)+n,i,c[i][j]);
			add(f(i,j)+n,j,c[i][j]);
		}
	}
	dinic();
	for(int i=head[S];i;i=e[i].next)if(e[i].cap) return 0;
	return 1;
}
int main(){
	freopen("kleague.in","r",stdin);freopen("kleague.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) w[i]=read(),read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) c[i][j]=read();
	for(int i=1;i<=n;i++) if(check(i)) printf("%d ",i);	
	fclose(stdin);fclose(stdout);
	return 0;
}