|
题目：http://www.sqyoj.club/problem.php?id=1016
思路：如果数i坐标在某幻灯片X范围内，则建立双向边，并增加数i的入度。遍历所点数，将入度为1的点存入栈。
从栈中取出一个数，并将该数连接的字母染色，再将该字母连接的数字的入度都减1，如果数字的入度是1，则将数字入栈。反复进行，直到栈空。如果栈内存入的数字刚好是n个，则说明可行，否则输出“None”。
这个操作与求拓扑排序的入度为0法的算法完全类似。
AC代码：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,m,x,y,stack[105],rd[105];
int x1[105],x2[105],y1[105],y2[105];
int a[105];
int cns,cnt,sum;
int num,head[105];
bool vis[105];
struct Edge{
int from,to,next;
};
Edge edge[215];
void join(int from,int to){
++num;
edge[num].next=head[from];
edge[num].from=from;
edge[num].to=to;
head[from]=num;
}
int main(){
memset(head,-1,sizeof(head));
cin>>n;
for(int i=1;i<=n;i++)
cin>>x1[i+'A'-1]>>x2[i+'A'-1]>>y1[i+'A'-1]>>y2[i+'A'-1];
for(int i=1;i<=n;i++){
cin>>x>>y;
for(int j=1;j<=n;j++)
if( x>x1[j+'A'-1] && x<x2[j+'A'-1]
&& y>y1[j+'A'-1] && y<y2[j+'A'-1] ){
join(j+'A'-1,i);
join(i,j+'A'-1);
rd[i]++;
}
}
for(int i=1;i<=n;i++)
if(rd[i]==1)stack[++cns]=i;
while(cns){
int nd=stack[cns];
cns--;
cnt++;
int from,to;
for(int i=head[nd];i!=-1;i=edge[i].next){
from=edge[i].to;
if(!vis[from]){
vis[from]=1;
a[from]=nd;
break;
}
}
for(int i=head[from];i!=-1;i=edge[i].next){
to=edge[i].to;
rd[to]--;
if(rd[to]==1){
cns++;
stack[cns]=to;
}
}
}
if(cnt==n)
for(int i=1;i<=n;i++)
printf("%c %d\n",i+'A'-1,a[i+'A'-1]);
else cout<<"None\n";
return 0;
}
| 
转播
