图论

_Xolotl_ · 2019-07-18 08:39:25 · 个人记录

图论

技巧

1.正常方法感觉做不出来时，考虑反向

# # # # # # # # # # #

topo

inline void topo()
{
    for(int i=1;i<=n;i++)
    {
        if(!in[i])
        {
            q.push(i);
            s[++tot]=i;
        }
    }
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        for(int i=head[top];i;i=edge[i].next)
        {
            int y=edge[i].to;
            in[y]--;
            if(!in[y])
            {
                q.push(y);
                s[++tot]=y;
            }
        }
    }
}

p2296 寻找道路

1.先使每条边反向

2.从终点跑一遍bfs，将可到达的点存入vis中，同时将他们存入ok中

3.筛一遍，将终点未能到达的点的终点设为不可走（不能用一开始的vis做处理，要用ok数组，因为这样可能会多删点，有些符合条件的点会被莫名其妙地被删掉）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
struct Edge{int to,nxt;}edge[200000+3];
int n,m;
int vis[10000+1];
queue<int> q;
int head[200000+2];
int ok[10000+2];
int cnt=1,st,en;
inline void add(int x,int y)
{
    edge[cnt].nxt=head[x];
    edge[cnt].to=y;
    head[x]=cnt++;
}
const int inf=0x3f3f;
int dist[10000+2];
inline void spfa(int s)
{
    for(int i=1;i<=n;i++)dist[i]=inf;
    dist[s]=0;
    q.push(s);
    vis[s]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=edge[i].nxt)
        {
            int y=edge[i].to;
            if(dist[y]>dist[x]+1&&ok[y])
            {
                dist[y]=dist[x]+1;
            //  cout<<y<<" "<<dist[y]<<endl;
                if(!vis[y])
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
void bfs(int s)
{
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=edge[i].nxt)
        {
            int y=edge[i].to;
            if(!vis[y])
            {
                vis[y]=1;
                q.push(y);
                ok[y]=1;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(y,x);
    }
    cin>>st>>en;
    ok[en]=1;
    bfs(en);
    //cout<<endl<<endl;
    /*for(int i=1;i<=n;i++)
    {
        cout<<i<<" "<<ok[i]<<endl;
    }*/
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            for(int j=head[i];j;j=edge[j].nxt)
            {
                int y=edge[j].to;
                if(ok[y])
                ok[y]=0;
            }
        }
    }
    //cout<<endl<<endl;
    /*for(int i=1;i<=n;i++)
    {
        cout<<i<<" "<<ok[i]<<endl;
    }*/
    memset(vis,0,sizeof(vis));
    spfa(en);
    if(dist[st]==0x3f3f)
    cout<<-1<<endl;
    else
    cout<<dist[st]<<endl;
    return 0;
}