记录编号	191364	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1638]贪婪之岛	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	2.268 s
提交时间	2015-10-07 14:35:44	内存使用	3.90 MiB

#include<cstdio>
#include<deque>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZEN=100000,SIZEM=410,maxn=0x7fffffff/2,BASE=100000;
int A,B,C,N,tot=0,S,T,ans=0,cnt=0,Z,sum;
int key[SIZEM],e[SIZEM];
int f[SIZEM];
deque<int> s[SIZEM],Pick;
class poi
{
public:
	int A,B,C;
	int id;
}P[SIZEN];
class miku
{
public:
	int fr,to,cap,flow,cost;
	miku(){}
	miku(int a,int b,int c,int d,int e)
	{
		fr=a,to=b,cap=c,flow=d,cost=e;
	}
}E[SIZEN];
void add(int fr,int to,int cap,int cost)
{
	s[fr].push_back(tot);
	E[tot++]=miku(fr,to,cap,0,cost);
	s[to].push_back(tot);
	E[tot++]=miku(to,fr,0,0,-cost);
}
void check()
{
	for(int i=S;i<=T;i++)
	{
		cout<<i<<endl;
		for(int j=0;j<s[i].size();j++)
		{
			miku v=E[s[i][j]];
			cout<<v.fr<<" "<<v.to<<" "<<v.cap<<" "<<v.flow<<" "<<v.cost<<endl;
		}
	}
}
bool cmp1(poi a,poi b){	
	if(a.A==b.A) return a.A+a.B+a.C>b.A+b.B+b.C;
	return a.A>b.A;
}
bool cmp2(poi a,poi b){	
	if(a.B==b.B) return a.A+a.B+a.C>b.A+b.B+b.C;
	return a.B>b.B;
}
bool cmp3(poi a,poi b){ 
	if(a.C==b.C) return a.A+a.B+a.C>b.A+b.B+b.C;
	return a.C>b.C;
}
bool cmp4(poi a,poi b){ return a.id<b.id;}
void read()
{
	scanf("%d",&N);
	scanf("%d%d%d",&A,&B,&C);
	for(int i=1;i<=N;i++)
	{		
		scanf("%d%d%d",&P[i].A,&P[i].B,&P[i].C);
		P[i].id=i;
	}
}
void gragh()
{
	for(int i=S;i<=T;i++) s[i].clear();tot=0;
	bool H[SIZEN]={0};
	bool PA[SIZEN]={0},PB[SIZEN]={0},PC[SIZEN]={0};
	sort(P+1,P+N+1,cmp1);
	for(int i=1;i<=A+B+C;i++) {H[P[i].id]=1;PA[P[i].id]=1;}
	sort(P+1,P+N+1,cmp2);
	for(int i=1;i<=A+B+C;i++) {H[P[i].id]=1;PB[P[i].id]=1;}
	sort(P+1,P+N+1,cmp3);
	for(int i=1;i<=A+B+C;i++) {H[P[i].id]=1;PC[P[i].id]=1;}
	sort(P+1,P+N+1,cmp4);
	cnt=0;
	Pick.clear();
	for(int i=1;i<=N;i++) if(H[i]) {Pick.push_back(i);cnt++;}
	S=0,T=cnt+4;
	add(0,cnt+1,A,0);add(0,cnt+2,B,0);add(0,cnt+3,C,0);
	for(int i=0;i<Pick.size();i++)
	{
		int j=Pick[i];
		if(PA[j]) add(cnt+1,i+1,1,P[j].A*BASE+P[j].A+P[j].B+P[j].C);
		if(PB[j]) add(cnt+2,i+1,1,P[j].B*BASE+P[j].A+P[j].B+P[j].C);
		if(PC[j]) add(cnt+3,i+1,1,P[j].C*BASE+P[j].A+P[j].B+P[j].C);
		add(i+1,T,1,0);
	}
}
bool spfa()
{
	deque<int> Q;
	bool inq[SIZEM]={0};
	for(int i=S;i<=T;i++)
	{
		f[i]=-maxn;
		key[i]=0;e[i]=0;
	}
	f[S]=0;inq[S]=1;Q.push_back(S);e[S]=maxn;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();inq[x]=0;
		for(int i=0;i<s[x].size();i++)
		{
			miku v=E[s[x][i]];
			if(v.cap<=v.flow) continue;
			if(f[x]+v.cost>f[v.to])
			{
				f[v.to]=f[x]+v.cost;
				key[v.to]=s[x][i];
				e[v.to]=min(e[x],v.cap-v.flow);
				if(!inq[v.to])
				{
					inq[v.to]=1;
					Q.push_back(v.to);
				}
			}
		}
	}
	if(f[T]==-maxn) return 0;
	return 1;
}
void dfs()
{
	int temp=T,now=e[T];
	//cout<<f[T]<<endl;
	ans+=now*f[T];
	while(temp!=S)
	{
		int i=key[temp];
		E[i].flow+=now;
		E[i^1].flow-=now;
		temp=E[i].fr;
	}
}
void work()
{
	ans=0;
	while(spfa()) dfs();
	//cout<<ans<<endl;
	printf("%d %d\n",ans/BASE,ans%BASE);
}
int main()
{
	freopen("greedyisland.in","r",stdin);
	freopen("greedyisland.out","w",stdout);
	scanf("%d",&Z);
	while(Z)
	{
		Z--;
		read();
		gragh();
		//check();
		work();
	}
	return 0;
}