1 条题解
-
0
C++ :
#include<cstdio> using namespace std; bool f=true; int n,num,top,matrix[30][30],ru[30],chu[30],zhan[30],ans[30]; struct Photo{//幻灯片 int Xmin,Xmax,Ymin,Ymax; }; Photo photo[30]; struct Node{ int x,y; }; Node node[30]; void PRINT() { for (int i=1; i<=n-1; i++) printf("%c %d\n",i+'A'-1,ans[i]);//强制类型转换的技巧 printf("%c %d",n+'A'-1,ans[n]); } int main() { scanf("%d",&n); for (int i=1; i<=n; i++) scanf("%d%d%d%d",&photo[i].Xmin,&photo[i].Xmax,&photo[i].Ymin,&photo[i].Ymax); for (int i=1; i<=n; i++) scanf("%d%d",&node[i].x,&node[i].y); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (node[j].x>=photo[i].Xmin&&node[j].x<=photo[i].Xmax&&node[j].y>=photo[i].Ymin&&node[j].y<=photo[i].Ymax) { matrix[i][j]=1;//不能用bush表存,不好操作.第i张幻灯片指向第j个点 chu[i]++; } for (int i=1; i<=n; i++) ru[i]=chu[i]-1;//入度为出度-1 while (num!=n) { int ss=0;//记录本次入度为0的点的个数,用来判断是否有环 for (int i=1; i<=n; i++) { if (ru[i]==0) { num++; ss++; zhan[++top]=i; for (int j=1; j<=n; j++) if (matrix[i][j]) { ans[i]=j; break; }//break 一点小优化:入度为0的点出度为1 ru[i]=0x7fffffff; //相当于开一个bool数组,每个点只入栈一次 } } if (ss==0) { f=false; break; } for (int i=1; i<=ss; i++)//去掉相连的边 { int now=zhan[top]; top--; for (int j=1; j<=n; j++) if (matrix[j][ans[now]]) { matrix[j][ans[now]]=0; ru[j]--; } } } if (f) PRINT(); else printf("None"); return 0; }
- 1
信息
- ID
- 1042
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者