记录编号	92815	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1638]贪婪之岛	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.501 s
提交时间	2014-03-22 21:52:16	内存使用	2.23 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=310,SIZEn=100200,INF=0x7fffffff/2,IND=100000;
class EDGE{
public:
	int from,to,cap,flow,cost;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
void addedge(int from,int to,int cap,int cost){
	edges.push_back((EDGE){from,to,cap,0,cost});
	edges.push_back((EDGE){to,from,0,0,-cost});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
int anscost=0;
int N,S,T;//0到N
bool SPFA(int S,int T){
	queue<int> Q;
	bool inq[SIZEN]={0};
	int f[SIZEN]={0};
	int father[SIZEN]={0};
	for(int i=0;i<=N;i++) f[i]=-INF;
	inq[S]=true;f[S]=0;Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			EDGE &now=edges[c[x][i]];
			if(now.flow>=now.cap) continue;
			if(f[x]+now.cost>f[now.to]){
				f[now.to]=f[x]+now.cost;
				father[now.to]=c[x][i];
				if(!inq[now.to]){
					inq[now.to]=true;
					Q.push(now.to);
				}
			}
		}
	}
	if(f[T]==-INF) return false;
	int nowflow=INF;
	int x=T;
	while(x!=S){
		EDGE &now=edges[father[x]];
		nowflow=min(nowflow,now.cap-now.flow);
		x=now.from;
	}
	anscost+=f[T]*nowflow;
	x=T;
	while(x!=S){
		edges[father[x]].flow+=nowflow;
		edges[father[x]^1].flow-=nowflow;
		x=edges[father[x]].from;
	}
	return true;
}
void work(void){
	anscost=0;
	while(SPFA(S,T));
	printf("%d %d\n",anscost/IND,anscost%IND);
}
int n;
int A,B,C;
class CARD{
public:
	int att,def,spe,sum;
	bool valid;
}card[SIZEn];
bool cmpa(CARD a,CARD b){
	if(a.att==b.att) return a.sum>b.sum;
	return a.att>b.att;
}
bool cmpb(CARD a,CARD b){
	if(a.def==b.def) return a.sum>b.sum;
	return a.def>b.def;
}
bool cmpc(CARD a,CARD b){
	if(a.spe==b.spe) return a.sum>b.sum;
	return a.spe>b.spe;
}
bool cmpv(CARD a,CARD b){
	return a.valid>b.valid;
}
int vacard=0;
void makegraph(void){
	edges.clear();
	N=vacard+4;
	S=0;
	T=N;
	for(int i=0;i<=N;i++) c[i].clear();
	int p1=N-3,p2=N-2,p3=N-1;
	addedge(S,p1,A,0);
	addedge(S,p2,B,0);
	addedge(S,p3,C,0);
	for(int i=1;i<=vacard;i++){
		addedge(p1,i,1,card[i].att*IND+card[i].sum);
		addedge(p2,i,1,card[i].def*IND+card[i].sum);
		addedge(p3,i,1,card[i].spe*IND+card[i].sum);
		addedge(i,T,1,0);
	}
}
void read(void){
	scanf("%d%d%d%d",&n,&A,&B,&C);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&card[i].att,&card[i].def,&card[i].spe);
	for(int i=1;i<=n;i++) card[i].sum=card[i].att+card[i].def+card[i].spe,card[i].valid=false;
	sort(card+1,card+1+n,cmpa);
	for(int i=1;i<=A+B+C;i++) card[i].valid=true;
	sort(card+1,card+1+n,cmpb);
	for(int i=1;i<=A+B+C;i++) card[i].valid=true;
	sort(card+1,card+1+n,cmpc);
	for(int i=1;i<=A+B+C;i++) card[i].valid=true;
	sort(card+1,card+1+n,cmpv);
	vacard=0;
	for(int i=1;i<=n;i++){
		if(card[i].valid) vacard++;
		else break;
	}
}
int main(){
	freopen("greedyisland.in","r",stdin);
	freopen("greedyisland.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		read();
		makegraph();
		work();
	}
	return 0;
}