P7860 求调
  • 板块题目总版
  • 楼主yrs2021
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/9/6 22:00
  • 上次更新2023/11/2 22:30:16
查看原帖
P7860 求调
555002
yrs2021楼主2023/9/6 22:00

一道拓扑排序的题,调不出来 题目 记录 15pts15pts 不知道为什么换成栈之后就 21pts21pts 了。

求调。

#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;
}
2023/9/6 22:00
加载中...