题解 P2752 【[USACO4.3]街道赛跑Street Race】

· · 题解

看楼下大佬们代码及其长，我这里提供一种更简洁的写法，不过思想大同小异。

主要分两步。

首先起点bfs一波，看i是不是必经点。

然后不用再搜索了，因为第一张子图的点集已确定，第二张子图的也就显而易见，遍历这个点集，假如有连向起点子图的就不满足。


#include<iostream>
#include<cstdio>
#define N 100
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,x,u,g[N][N],in[N],l,r,q[N],ans[N],mus[N],yes;
int main(){
    scanf("%d",&x);
    while(x!=-1){
        while(x!=-2 && x!=-1) g[n][x]=1,scanf("%d",&x);
        scanf("%d",&x),n++;
    }n--,in[0]=1;
    FOR(i,1,n-1){
        FOR(v,1,n) in[v]=0;
        l=1,r=2;
        while(l<r){
            u=q[l++];
            FOR(v,0,n) if(g[u][v] && in[v]==0 && v!=i)
                in[v]=1,q[r++]=v;
        }if(in[n]==0){
            mus[++mus[0]]=i,yes=1;
            FOR(v,0,n)if(!in[v])
            FOR(w,0,n)if(g[v][w] && in[w]) yes=0;
            if(yes) ans[++ans[0]]=i;
        }
    }
    FOR(i,0,mus[0]) printf("%d ",mus[i]);printf("\n");
    FOR(i,0,ans[0]) printf("%d ",ans[i]);
}```