#include <myhead.h>

// 线段树做法
#define ROOT(a) 1,(a),1 

class Data
{
public:
	bool input();
	void work();
	inline void output();
private:
	enum{N=101,M=101};
	bool graph[N][M];
	int n,m,vNum,res;
	int maxDataA[N],maxDataB[M];
	int segA[N<<3],segB[N<<3];
	inline void initData();
	inline int maxNode(int,int,int *);
	inline void pushUp(int,int *,int *);
	void build_Seg(int,int,int,int*,int*);
	inline void upDataA();
	inline void upDataB();
	void upSeg(int,int,int,int,int *,int *);
	inline void clearNode(int,int,int *,int *);
};

void Data::initData()
{
	res=0;
	memset(graph,false,sizeof(graph));
	memset(maxDataA,0,sizeof(maxDataA));
	memset(maxDataB,0,sizeof(maxDataB));
}

bool Data::input()
{
	if(scanf("%d",&n),!n)
		return false;
	scanf("%d%d",&m,&vNum);
	initData();
	int mm,x,y;
	int t=vNum;
	while(t--) {
		scanf("%d%d%d",&mm,&x,&y);
		if(x*y==0) {
			vNum--;
			continue;
		}
		graph[x][y]=true;
		maxDataA[x]++;
		maxDataB[y]++;
	}
	build_Seg(ROOT(n),maxDataA,segA);
	build_Seg(ROOT(m),maxDataB,segB);
	return true;
}

int Data::maxNode(int x,int y,int *maxData)
{
	return maxData[x]>=maxData[y]?x:y;
}

void Data::pushUp(int rt,int *maxData,int *seg)
{
	seg[rt]=maxNode(seg[LL(rt)],seg[RR(rt)],maxData);
}

void Data::build_Seg(int l,int r,int rt,int *maxData,int *seg)
{
	if(l==r) {
		seg[rt]=l;
		return ;
	}
	int mid=MID(l,r);
	build_Seg(LSON,maxData,seg);
	build_Seg(RSON,maxData,seg);
	pushUp(rt,maxData,seg);
}

void Data::clearNode(int num,int node,int *maxData,int *seg)
{
	maxData[node]=1;
	upSeg(ROOT(num),node,maxData,seg);
}

void Data::work()
{
	int nn;
	do{
		if(maxDataA[segA[1]]>=maxDataB[segB[1]]) {
			nn=maxDataA[segA[1]];
			upDataA();
			clearNode(n,segA[1],maxDataA,segA);
		}
		else {
			nn=maxDataB[segB[1]];
			upDataB();
			clearNode(m,segB[1],maxDataB,segB);
		}
		res++;
		vNum-=nn;
	}while(vNum);
}

void Data::upDataA()
{
	int k=segA[1];
	for(int i=1;i<m;++i) {
		if(graph[k][i]) {
			graph[k][i]=false;
			upSeg(ROOT(m),i,maxDataB,segB);
		}
	}
}

void Data::upDataB()
{
	int k=segB[1];
	for(int i=1;i<n;++i) {
		if(graph[i][k]) {
			graph[i][k]=false;
			upSeg(ROOT(n),i,maxDataA,segA);
		}
	}
}

void Data::upSeg(int l,int r,int rt,int s,int *maxData,int *seg)
{
	if(l==r) {
		maxData[l]--;
		return ;
	}
	int mid=MID(l,r); 
	if(s<=mid)
		upSeg(LSON,s,maxData,seg);
	else
		upSeg(RSON,s,maxData,seg);
	pushUp(rt,maxData,seg);
}

void Data::output()
{
	printf("%d\n",res);
}

int main()
{
	Data data;
	while(data.input()) {
		data.work();
		data.output();
	}
	return 0;
}

• Re:无聊用线段树试了试 谁能告诉我为什么超时么~ (27) lucky_purple 2012-10-29 20:04:10