M_sea

洛谷2752 街道赛跑Street Race
Luogu算法第一问很简单,把每个点去掉再Dfs即可。第二问首先可以发现,第二问的答案一定是第一问答案的子集。那么...
扫描右侧二维码阅读全文
22
2017/11

洛谷2752 街道赛跑Street Race

Luogu

算法

第一问

很简单,把每个点去掉再Dfs即可。

第二问

首先可以发现,第二问的答案一定是第一问答案的子集。

那么就很好办了。从节点i出发,若能Dfs到一个去掉i后从0出发能够Dfs到的节点,则i不是“中间路口”。

那么只要在判出第一问时顺便判了第二问即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

const int N=50+5,M=100+5;

int g[N][N];
bool vis[N],vis2[N];
int n,m;

inline void addEdge(int u,int v) { g[u][v]=1; }
inline void Init() {
    int u=0,v;
    while (u!=-2) {
        v=read(); 
        if (v==-2) break;
        while (v!=-2) { addEdge(u,v); v=read(); }
        u++;
    }
    n=u; v=read();
}

inline bool Dfs1(int u) {
    if (vis[u]) return false;
    if (u==n) return true;
    vis[u]=true;
    for (re int i=0;i<=n;i++) {
        int v=i;
        if (g[u][v]&&!vis[v])
            if (Dfs1(v)) return true;
    }
    return false;
}
inline bool Dfs2(int u) {
    if (vis[u]) return true;
    if (vis2[u]) return false;
    vis2[u]=true;
    for (re int i=0;i<=n;i++) {
        int v=i;
        if (g[u][v]&&!vis2[v])
            if (Dfs2(v)) return true;
    }
    return false;
}

int ans1[N],num1=0;
int ans2[N],num2=0;
int main() {
    Init();
    for (re int i=1;i<n;i++) {
        memset(vis,false,sizeof(vis));
        memset(vis2,false,sizeof(vis2));
        vis[i]=true;
        if (!Dfs1(0)) {
            ans1[++num1]=i; vis[i]=false;
            if (!Dfs2(i)) ans2[++num2]=i;
        }
    }
    printf("%d ",num1);
    for (re int i=1;i<=num1;i++) printf("%d ",ans1[i]);
    putchar('\n');
    printf("%d ",num2);
    for (re int i=1;i<=num2;i++) printf("%d ",ans2[i]);
    putchar('\n');
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 40 PM

发表评论