Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 无聊用线段树试了试 谁能告诉我为什么超时么~

Posted by lucky_purple at 2012-10-29 20:02:07 on Problem 1325
```#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;
}
```

Followed by: