NOIP2013 货车运输

题目:

   国有 座城市,编号从 ,城市之间有 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

代码:

  • 启发式合并:
      把边从大到小排序,每次用一条边去合并两个点集。当询问的两个端点被放入同一集合时,这个两点间最大最小值的就是这条边的权值。复杂度
  • 最大生成树和树上倍增:
      货车行走的路径一定是在最大生成树上的,所以可以先造出最大生成树。在树上两点的路径是唯一的,所以直接倍增查两点间最小值即可。复杂度
  • 整体二分:
      如果考虑用二分解决这题的话,不难想到二分路径上的最小边权,把所有大于等于二分当前值的边放入图中,用并查集判断询问的两点是否联通。这样的复杂度是。直接TLE。
      考虑到并查集不单单只能查询一个询问的两个端点,所以考虑对每个询问单独维护一个二分的状态()。把询问根据排序,按顺序计算询问,那么每条边就只用被加入一次。复杂度就变成了

代码:

  • 启发式合并:
#include <bits/stdc++.h>
#define MN 10005
#define clr(a,b) memset(a,b,sizeof a)
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
using namespace std;
int ufs[MN];
struct Ques{
    int u,id;
};
vector<Ques> que[MN];
int find(int x){return x==ufs[x]?x:ufs[x]=find(ufs[x]);}
struct Edge{
    int u,v,l;
    bool operator < (const Edge &x) const {
        return l>x.l;
    }
};
int ans[30005];
void merge(int x,int y,int val){
    x=find(x);y=find(y);
    if(x==y)return;
    if(que[x].size()<que[y].size())
        swap(x,y);
    ufs[y]=x;
    FOR(i,0,(int)que[y].size()-1){
        int now=que[y][i].u,id=que[y][i].id;
        if(~ans[id])continue;
        if(find(now)==x)ans[id]=val;
        else que[x].push_back(que[y][i]);
    }
    que[y].clear();
}
Edge e[50005];
int main(){
    int n,m,q;
    scanf("%d%d",&n,&m);
    FOR(i,1,n)ufs[i]=i;
    FOR(i,1,m){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        e[i]=(Edge){a,b,c};
    }
    sort(e+1,e+1+m);
    scanf("%d",&q);
    FOR(i,1,q){
        int a,b;
        scanf("%d%d",&a,&b);
        que[a].push_back((Ques){b,i});
        que[b].push_back((Ques){a,i});
    }
    clr(ans,-1);
    FOR(i,1,m){
        Edge now=e[i];
        merge(now.u,now.v,now.l);
    }
    FOR(i,1,q)printf("%d\n",ans[i]);
    return 0;
}
  • 最大生成树和树上倍增:
#include <bits/stdc++.h>
#define MN 10005
#define inf 2100000000
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
};
struct Edge{int to,w;};
Link<MN,MN<<1,Edge> tre;
template<int N> struct UFS{
    int ufs[N];
    void init(int n){FOR(i,1,n)ufs[i]=i;}
    int find(int x){return ufs[x]==x?x:ufs[x]=find(ufs[x]);}
    int& operator [] (int x){
        x=find(x);
        return ufs[x];
    }
};
template<int N,int M> struct Kruskal{
    struct EDGE{
        int u,v,l;
        bool operator < (const EDGE &x) const {
            return l>x.l;
        }
    };
    EDGE e[M];
    UFS<N> ufs;
    int tot;
    Kruskal(){tot=0;}
    void addEdge(int a,int b,int c){e[++tot]=(EDGE){a,b,c};}
    void solve(int n){
        int cnt=0;
        sort(e+1,e+1+tot);
        ufs.init(n);
        FOR(i,1,tot){
            int u=e[i].u,v=e[i].v;
            if(ufs[u]==ufs[v])continue;
            tre.add(u,(Edge){v,e[i].l});
            tre.add(v,(Edge){u,e[i].l});
            ufs[u]=ufs[v];
            cnt++;
            if(cnt==n-1)return;
        }
    }
};
template<int N> struct Tree{
    int fa[N][20],Min[N][20],vis[N],dep[N];
    void dfs(int o,int f,int w,int flag){
        fa[o][0]=f;Min[o][0]=w;
        dep[o]=dep[f]+1;vis[o]=flag;
        EOR(k,tre,o){
            Edge e=tre[k];
            if(e.to==f)continue;
            dfs(e.to,o,e.w,flag);
        }
    }
    void init(int n){
        FOR(i,1,n)if(!vis[i])
            dfs(i,0,inf,i);
        FOR(k,1,17)
            FOR(o,1,n){
                fa[o][k]=fa[fa[o][k-1]][k-1];
                Min[o][k]=min(Min[o][k-1],Min[fa[o][k-1]][k-1]);
            }
    }
    int query(int u,int v){
        if(vis[u]!=vis[v])return -1;
        if(dep[u]<dep[v])swap(u,v);
        int d=dep[u]-dep[v],ans=inf;
        FOR(k,0,17)if(d>>k&1){
            tomin(ans,Min[u][k]);
            u=fa[u][k];
        }
        if(u==v)return ans;
        DOR(k,17,0)if(fa[u][k]!=fa[v][k]){
            tomin(ans,Min[u][k]);
            tomin(ans,Min[v][k]);
            u=fa[u][k];v=fa[v][k];
        }
        tomin(ans,Min[u][0]);
        tomin(ans,Min[v][0]);
        return ans;
    }
};
Tree<MN> tree;
Kruskal<MN,50005> kruskal;
int main(){
    int n,m,q;
    scanf("%d%d",&n,&m);
    FOR(i,1,m){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        kruskal.addEdge(a,b,c);
    }
    kruskal.solve(n);
    tree.init(n);
    scanf("%d",&q);
    FOR(i,1,q){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",tree.query(a,b));
    }
    return 0;
}
  • 整体二分:
#include <bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof a)
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
#define inf 2100000000
using namespace std;
template<int N> struct UFS{
    int ufs[N];
    void init(int n){FOR(i,1,n)ufs[i]=i;}
    int find(int x){return ufs[x]==x?x:ufs[x]=find(ufs[x]);}
    int& operator [] (int x){
        x=find(x);
        return ufs[x];
    }
};
int n,m,q;
struct Edge{
    int u,v,w;
    bool operator < (const Edge &x) const {
        return w>x.w;
    }
};
Edge e[50005];
struct Data{
    int u,v,L,R,mid,id;
    bool operator < (const Data &x) const {
        return mid>x.mid;
    }
};
Data Q[30005];
int ans[30005];
UFS<10005> ufs;
void solve(){
    while(true){
        bool flag=true;
        FOR(i,1,q){
            if(Q[i].L>Q[i].R)Q[i].mid=-inf;
            else Q[i].mid=Q[i].L+Q[i].R>>1,flag=false;
        }
        if(flag)return;
        sort(Q+1,Q+1+q);
        ufs.init(n);
        int j=1;
        FOR(i,1,q){
            if(Q[i].mid==-inf)break;
            while(j<=m&&e[j].w>=Q[i].mid){
                ufs[e[j].u]=ufs[e[j].v];
                j++;
            }
            if(ufs[Q[i].u]==ufs[Q[i].v])
                ans[Q[i].id]=Q[i].mid,Q[i].L=Q[i].mid+1;
            else
                Q[i].R=Q[i].mid-1;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,m){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        e[i]=(Edge){a,b,c};
    }
    sort(e+1,e+1+m);
    scanf("%d",&q);
    FOR(i,1,q){
        int a,b;
        scanf("%d%d",&a,&b);
        Q[i]=(Data){a,b,0,100000,0,i};
    }
    clr(ans,-1);
    solve();
    FOR(i,1,q)printf("%d\n",ans[i]);
    return 0;
}