[UOJ 19]寻找道路

这个题难就难在,别说重边自环,就是简单有向环,也会让DFS爆炸。所以考虑BFS。

但……BFS怎么判断其他点到[tex]t[/tex]的联通?

方法是,把边都反过来!这样BFS一遍就可以判联通了。

然后接下来BFS最短路就简单了,注意一些特判。

代码:

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=10005,maxm=400005;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxm],to[maxm];
bool rev[maxm];
int graph_tot=0;
inline void AddEdge(int u,int v,bool reverse=false){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
    rev[graph_tot]=reverse;
}

int s,t;
bool vis[maxn];
bool LT[maxn];
bool bfs_1(){
    register int i,u;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(t);
    vis[t]=true;
    LT[t]=true;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        GRAPH_REP(i,u){
            if(rev[i] && !vis[to[i]]){
                LT[to[i]]=true;
                Q.push(to[i]);
                vis[to[i]]=true;
            }
        }
    }
    return LT[s];
}

int dep[maxn];
int bfs_2(){
    register int i,u;
    bool Allow;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s]=true;
    dep[s]=0;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        Allow=true;
        GRAPH_REP(i,u){
            if(!rev[i] && !LT[to[i]]){
                Allow=false;
                break;
            }
        }
        if(!Allow)
            continue;
        GRAPH_REP(i,u){
            if(!rev[i] && !vis[to[i]]){
                dep[to[i]]=dep[u]+1;
                Q.push(to[i]);
                vis[to[i]]=true;
            }
        }
    }
    return vis[t]?dep[t]:-1;
}

int main(){
    int n,m,u,v;
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u,true);
    }
    scanf("%d%d",&s,&t);
    if(!bfs_1()){
        puts("-1");
    }else{
        printf("%d\n",bfs_2());
    }
    return 0;
}

[BZOJ 1050]旅行/[CodeVS 1001]舒适的路线

这两个题是一样的啊……

让路径上最大值最小当然要玩瓶颈路,瓶颈路需要MST,然后Kruskal求MST时最小边不是不可控的!也就是说我们可以控制最小边,从而求出符合要求的生成树,然后凿出瓶颈路。

所以我们可以直接枚举最小边,然后Kruskal求生成树,之后求瓶颈路。至于是否有解,第一遍Kruskal(第一遍求的其实是MST)之后看看是否联通即可。

不过这个题求瓶颈路个人建议用BFS而不是DFS,且不谈BFS效率高还不易炸堆栈段(尽管这个题没有炸堆栈段的隐患),DFS本身细节就很多,容易错。

代码:

/**************************************************************
    Problem: 1050
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3588 ms
    Memory:1172 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <bitset>
#include <vector>
#include <queue>
using namespace std;
const int maxn=501,maxm=10001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REPB(i,n) for(i=1;i<=(n);i++)
#define CUS_REP(i,u,v) for(i=(u);i<(v);i++)
#define REP_G(i,u) for(i=first[u];i;i=next[i])
#define CL_ARR(x,v) memset(x,v,sizeof(x))
typedef pair<int,int> pii;
int n;
int S,T;
 
// Graph
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int G_cnt=0;
inline void Add_Edge(int u,int v,int d){
    G_cnt++;
    next[G_cnt]=first[u];
    first[u]=G_cnt;
    to[G_cnt]=v;
    dist[G_cnt]=d;
}
inline void Clear_Graph(){
    CL_ARR(first,0);
    CL_ARR(next,0);
    CL_ARR(to,0);
    CL_ARR(dist,0);
    G_cnt=0;
}
 
// BFS
bitset<maxn> vis;
struct Node{
    int x,maxv,minv;
};
pii BFS(){
    register int a,b,i;
    queue<Node> Q;
    Node tt;
    Q.push((Node){S,-1,0x7fffffff});
    vis[S]=true;
    while(!Q.empty()){
        tt=Q.front();
        Q.pop();
        if(tt.x==T)
            return make_pair(tt.maxv,tt.minv);
        REP_G(i,tt.x){
            if(!vis[to[i]]){
                vis[to[i]]=true;
                Q.push((Node){to[i],max(tt.maxv,dist[i]),min(tt.minv,dist[i])});
            }
        }
    }
}
 
// BINGCHA Set
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    CL_ARR(rank,0);
}
 
// MST
struct Edge{
    int u,v,d;
    bool operator <(const Edge& x) const{
        return d<x.d;
    }
};
vector<Edge> E;
bool OK=false;
pii ans;
void MST(int x){
    register int i,a,b,cnt=0;
    pii que;
    register double jia,yi;
    Clear_Graph();
    init_set();
    CUS_REP(i,x,E.size()){
        if(!is_same(E[i].u,E[i].v)){
            Add_Edge(E[i].u,E[i].v,E[i].d);
            Add_Edge(E[i].v,E[i].u,E[i].d);
            cnt++;
            union_set(E[i].u,E[i].v);
            if(cnt==n-1)
                break;
        }
    }
    if(is_same(S,T)){
        OK=true;
    }else{
        return;
    }
    vis.reset();
    que=BFS();
    a=que.first;
    b=que.second;
    jia=((double)a)/((double)b);
    yi=(double(ans.first))/(double(ans.second));
    if(jia<yi){
        ans.first=a;
        ans.second=b;
    }
}
 
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main(){
    int m;
    register int i,u,v,d;
    n=readint();
    m=readint();
    REP(i,m){
        u=readint();
        v=readint();
        d=readint();
        E.push_back((Edge){u,v,d});
    }
    S=readint();
    T=readint();
    sort(E.begin(),E.end());
    ans.first=0x7fffffff;
    ans.second=1;
    REP(i,m){
        MST(i);
        if(!OK){
            if(!i){
                puts("IMPOSSIBLE");
                return 0;
            }else{
                break;
            }
        }
    }
    d=gcd(ans.first,ans.second);
    ans.first/=d;
    ans.second/=d;
    if(ans.second==1)
        printf("%d\n",ans.first);
    else
        printf("%d/%d\n",ans.first,ans.second);
    return 0;
}