一道拓扑排序的题,调不出来 题目 记录 15pts 不知道为什么换成栈之后就 21pts 了。
求调。
#include<bits/stdc++.h>
#define T 10100
#define N 5010
using namespace std;
int re,n,maxx,minn=0x3fffffff,x1,x2,y11,y2,e[N*N],ne[N*N],hd[N*N],idx;
queue<int> q;
char c;
struct node{
int x1,y1,x2,y2,id,point;
} line[N];
int read(){
re=0;
c=getchar();
while(c<'0'||c>'9'){
c=getchar();
}
while(c>='0'&&c<='9'){
re=(re<<3)+(re<<1)+(c^48);
c=getchar();
}
return re;
}
void write(int x){
if(x/10){
write(x/10);
}
putchar(x%10|48);
}
bool cmp(node x,node y){
return x.y1==y.y1?x.y2<y.y2:x.y1<y.y1;
}
void bfs(){
while(!q.empty()){
int u = q.front();
q.pop();
write(line[u].id);
putchar(' ');
for(int i = hd[u];i;i=ne[i]){
int j=e[i];
line[j].point--;
if(line[j].point==0){
q.push(j);
}
}
}
}
void add(int a,int b){
e[++idx]=b;
ne[idx]=hd[a];
hd[a]=idx;
}
int main(){
n=read();
for(int i = 1;i<=n;i++){
line[i].id=i;
x1=read();
y11=read();
x2=read();
y2=read();
int min1=min(x1,x2),min2=min(y11,y2);
int max1=max(x1,x2),max2=max(y11,y2);
line[i].x1=min1;
line[i].y1=min2;
line[i].x2=max1;
line[i].y2=max2;
maxx=max(max1,maxx);
minn=min(min1,minn);
}
sort(line+1,line+1+n,cmp);
line[0].x1=0x3fffffff;
line[0].x2=0x3fffffff;
for(int i = 1;i<=n;i++){
for(int j = 1;j<i;j++){
if((line[j].x1>=line[i].x1&&line[j].x1<line[i].x2)||(line[j].x2>line[i].x1&&line[j].x2<=line[i].x2)||(line[j].x1<line[i].x1&&line[j].x2>line[i].x2)){
add(j,i);
line[i].point++;
}
}
if(!line[i].point){
q.push(i);
}
}
bfs();
return 0;
}