USACO 4.3.3 Street Race
对于第一问可以枚举每个点,如果没有这个点看能不能从0到N,如果能就说明这个点不是unavoidable点,这样的复杂度是定点数*变数,然后对于第二问的话,我们可以从第一问的答案里面再枚举,也就是说,如果是第一问的答案才有可能成为第二问的答案,这样的话,枚举第二问的时候只要考虑一下,split点一定是一个的起点,另一个的终点,然后没重边,然后不能有边从一个区域到另一个区域,终点的出度为0.其他的就没什么了.
代码如下:
/
ID:qcx97811
LANG:C
TASK:race3
/
#include
#include
#include
#include
int v,e
int graph[56][56],used[56];//graph表示原图
void bfs(int s,int n)
{//bfs搜索起点为s不经过n点的所有点,这里可以不传n
//直接used[n]=1就行了
int rear,front,i,j
int q[56];
memset(used,0,sizeof(used));
q[rear=0]=s;
used[0]=1
front=-1
while(front<rear)
{
i=q[++front];
for(j=0j<v;j++)
{
if(j != n & 0==used[j]&&graph[i][j]>0)
{
q[++rear]=j
used[j]=1
}
}
}
}
void work()
{
int i,ans[56],bans[56],j,k//ans是第一问的答案 bans是第二问的答案
int sum=0,bsum=0//sum是第一问的答案个数 bsum是第二问的答案个数
int f
for(i=0i<v-1;i++)
{
bfs(0,i);
if(0==used[v-1])
{//如果不能到达终点的话说明这个点是unavoidable点
ans[sum]=i
sum++
}
}
printf(“%d”,sum);
for(i=0i<sum;i++)
printf(“ %d”,ans[i]);
printf(“\n“);
for(i=0i<sum;i++)
{//枚举第一问中的点
f=1
bfs(0,ans[i]);
for(j=0j<v & f;j++)
{
if(1 == used[j])
{
for(k=0k<v & f;k++)
{
if(k != ans[i] & 0 == used[k] && graph[j][k]>0)
{
f=0
}
if(1==used[k] & graph[ans[i]][k]>0)
f=0 //终点的出度必须为0
}
}
}
used[ans[i]]=1
for(j=0j<v&f;j++)
{
if(0 == used[j] & ans[i]!=j)
{
for(k=0k<v&f;k++)
{
if(k != ans[i] & 1 == used[k] && graph[j][k] > 0)
f=0
}
}
}
if(1 == f)
{
bans[bsum++]=ans[i];
}
}
printf(“%d”,bsum);
for(i=0i<bsum;i++)
printf(“ %d”,bans[i]);
printf(“\n“);
}
int main(void)
{
freopen(“race3.in”,“r”,stdin);
freopen(“race3.out”,“w”,stdout);
int i,j
v=e=0
memset(graph,-1,sizeof(graph));
while(1)
{
scanf(“%d”,i);
if(-1 == i)
break
while(-2 != i)
{
graph[v][i]=1
scanf(“%d”,i);
}
v++
}
#if 0
for(i=0;i
{
for(j=0;j
printf(“%d “,graph[i][j]);
printf(“\n”);
}
#endif
work();
return 0
}
ID:qcx97811
LANG:C
TASK:race3
/
#include
#include
#include
#include
int v,e
int graph[56][56],used[56];//graph表示原图
void bfs(int s,int n)
{//bfs搜索起点为s不经过n点的所有点,这里可以不传n
//直接used[n]=1就行了
int rear,front,i,j
int q[56];
memset(used,0,sizeof(used));
q[rear=0]=s;
used[0]=1
front=-1
while(front<rear)
{
i=q[++front];
for(j=0j<v;j++)
{
if(j != n & 0==used[j]&&graph[i][j]>0)
{
q[++rear]=j
used[j]=1
}
}
}
}
void work()
{
int i,ans[56],bans[56],j,k//ans是第一问的答案 bans是第二问的答案
int sum=0,bsum=0//sum是第一问的答案个数 bsum是第二问的答案个数
int f
for(i=0i<v-1;i++)
{
bfs(0,i);
if(0==used[v-1])
{//如果不能到达终点的话说明这个点是unavoidable点
ans[sum]=i
sum++
}
}
printf(“%d”,sum);
for(i=0i<sum;i++)
printf(“ %d”,ans[i]);
printf(“\n“);
for(i=0i<sum;i++)
{//枚举第一问中的点
f=1
bfs(0,ans[i]);
for(j=0j<v & f;j++)
{
if(1 == used[j])
{
for(k=0k<v & f;k++)
{
if(k != ans[i] & 0 == used[k] && graph[j][k]>0)
{
f=0
}
if(1==used[k] & graph[ans[i]][k]>0)
f=0 //终点的出度必须为0
}
}
}
used[ans[i]]=1
for(j=0j<v&f;j++)
{
if(0 == used[j] & ans[i]!=j)
{
for(k=0k<v&f;k++)
{
if(k != ans[i] & 1 == used[k] && graph[j][k] > 0)
f=0
}
}
}
if(1 == f)
{
bans[bsum++]=ans[i];
}
}
printf(“%d”,bsum);
for(i=0i<bsum;i++)
printf(“ %d”,bans[i]);
printf(“\n“);
}
int main(void)
{
freopen(“race3.in”,“r”,stdin);
freopen(“race3.out”,“w”,stdout);
int i,j
v=e=0
memset(graph,-1,sizeof(graph));
while(1)
{
scanf(“%d”,i);
if(-1 == i)
break
while(-2 != i)
{
graph[v][i]=1
scanf(“%d”,i);
}
v++
}
#if 0
for(i=0;i
{
for(j=0;j
printf(“%d “,graph[i][j]);
printf(“\n”);
}
#endif
work();
return 0
}
