danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29173

[BZOJ 3732]Network

2016年9月04日 11:45 | Comments(0) | Category:题解 | Tags:

这水体太热情了……和那个运输路线那个题是一样的。

本质是求最小瓶颈路。造出来MST倍增LCA维护一波即可。

代码:

/**************************************************************
    Problem: 3732
    User: danihao123
    Language: C++
    Result: Accepted
    Time:340 ms
    Memory:4344 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=15005,maxm=30005;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
 
// Graph
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
// DFS
int dep[maxn];
int anc[maxn][16],maxcost[maxn][16];
void dfs(int x,int fa,int depth,int dis){
    int i;
    dep[x]=depth;
    anc[x][0]=fa;
    maxcost[x][0]=dis;
    GRAPH_REP(i,x){
        if(to[i]!=fa){
            dfs(to[i],x,depth+1,dist[i]);
        }
    }
}
 
// Doubling LCA
int n;
inline void process(){
    register int i,j,a;
    dfs(1,-1,0,0);
    for(j=1;(1<<j)<n;j++)
        REP_B(i,n){
            if(anc[i][j-1]!=-1){
                a=anc[i][j-1];
                anc[i][j]=anc[a][j-1];
                maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
            }
        }
}
int query(int x,int y){
    register int i,j,log,ans=0;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;(1<<log)<=dep[x];log++);
    log--;
    for(j=log;j>=0;j--)
        if(dep[x]-(1<<j)>=dep[y]){
            ans=max(ans,maxcost[x][j]);
            x=anc[x][j];
        }
    if(x==y)
        return ans;
    for(j=log;j>=0;j--)
        if(anc[x][j]!=-1 && anc[x][j]!=anc[y][j]){
            ans=max(ans,max(maxcost[x][j],maxcost[y][j]));
            x=anc[x][j];
            y=anc[y][j];
        }
    ans=max(ans,max(maxcost[x][0],maxcost[y][0]));
    return ans;
}
 
// Disjoint 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]);
}
inline 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;
    REP_B(i,n)
        p[i]=i;
    // CL_ARR(rank,0);
}
 
// MST
#define EDGE_ALL(i) E[i].u,E[i].v
struct Edge{
    int u,v,d;
    bool operator <(const Edge& x) const{
        return d<x.d;
    }
};
Edge E[maxm];
int m;
void MST(){
    register int i,cnt=0;
    init_set();
    sort(E+1,E+1+m);
    REP_B(i,m){
        if(!is_same(EDGE_ALL(i))){
            cnt++;
            union_set(EDGE_ALL(i));
            AddEdge(EDGE_ALL(i),E[i].d);
            AddEdge(E[i].v,E[i].u,E[i].d);
        }
        if(cnt==(n-1))
            break;
    }
    process();
}
 
int main(){
    int q,u,v;
    register int i;
    scanf("%d%d%d",&n,&m,&q);
    REP_B(i,m){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
    }
    MST();
    while(q--){
        scanf("%d%d",&u,&v);
        printf("%d\n",query(u,v));
    }
    return 0;
}

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

2016年8月15日 13:32 | Comments(0) | Category:题解 | Tags:

这两个题是一样的啊……

让路径上最大值最小当然要玩瓶颈路,瓶颈路需要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;
}