最小树形图

个人理解就是求指定起点的有向图的最小生成树。

算法的大概步骤如下：

1. 遍历所有边，求得一步到达点v的距离in[v]和前驱pre[v].(若除根节点外有的点不可以被到达则无解)
2. 遍历所有点v,ans+in[v] (相当于从离v最近的点走到了v),看其是否在环上(一直跑pre,能跑到他自己说明在环上),若在环上则将环上的点缩成一个新点id[cnt++]
3. 若一个环也没有找到,则最小树形图构建完成,返回ans
4. 否则,将所有单点也构造成新点id[cnt++],更新边上点的编号和边权,若边的两端不在一个点边权要减去in[v] (2中ans已经加上in[v],及不管从那条边走到v,都已经走过in[v]了,至于在一个新点时,个人理解为环已经被缩成一个点,环上的边已经不会再走了)

LightOJ 1384

构建联通网络的花费就是最小树形图,二分最小的带宽然后重新建图,跑最小树形图是否小于最大花费.

#include<bits/stdc++.h>
#define ll long long
#define ls(r)   r<<1
#define rs(r)   r<<1|1
using namespace std;
const int N = 1e3+10;
const int INF = 0x3f3f3f3f;

struct edge{
    int u,v,w,cost;
    edge(int u,int v,int w,int cost):u(u),v(v),w(w),cost(cost){}
    edge(){}
};

struct directed_MT{
    int n,m;
    edge e[N*10];
    int vis[N],pre[N],id[N],in[N];  // 是否被访问过,前驱节点,新点编号,前驱到他的距离
    void init(int _n){n = _n; m = 0;}
    void add(int u,int v,int w){e[m++] = edge(u,v,w,0);}

    int dirMt(int sp){
        int ans = 0;
        while(1){
            for(int i=0;i<n;++i)    in[i] = INF;    // 初始化
            for(int i=0;i<m;++i){
                int u = e[i].u;
                int v = e[i].v;
                // 更新v的距离，和前驱
                if(e[i].w < in[v] && u!=v){
                    in[v] = e[i].w;
                    pre[v] = u;
                }                
            }
            for(int i=0;i<n;++i){
                if(i==sp) continue;
                // 无法到达 i 点 不连通
                if(in[i] == INF)    return -1;
            }
            int cnt = 0;    // 新图点的数量
            memset(id,-1,sizeof id);
            memset(vis,-1,sizeof vis);
            in[sp] = 0; // 初始点不要钱
            for(int i=0;i<n;++i){
                ans += in[i];   // 加上到这个点的距离
                int v = i;
                // 找自环
                while(vis[v]!=i && id[v]==-1 && v!=sp){
                    vis[v] = i;
                    v = pre[v];
                }
                if(v!=sp && id[v] ==-1){    // 缩点
                    for(int u=pre[v];u!=v;u=pre[u]) 
                        id[u] = cnt;
                    id[v] = cnt++;
                }
            }
// cerr << cnt << ' ' ;
            if(cnt==0)  break;  // 没有自环 算法截止
            for(int i=0;i<n;++i)    // 一个点构成一个环
                if(id[i]==-1)   id[i] = cnt++;
            for(int i=0;i<m;++i){  // 重新构图
                int v = e[i].v;
                e[i].v = id[e[i].v];
                e[i].u = id[e[i].u];
                if(e[i].v != e[i].u)    // 加不加貌似无所谓
                    e[i].w -= in[v];    // 已经可以到达v，所以到v的距离要减去
            }
            n = cnt;
            sp = id[sp];    // 更新节点个数和根节点
        }
        return ans;
    }
}MT;
edge e[N*10];
int n,m,c;
int check(int k){
    MT.init(n);
    for(int i=1;i<=m;++i){
        if(e[i].cost>=k)   MT.add(e[i].u,e[i].v,e[i].w);
    }
    int res =  MT.dirMt(0);
    return res <= c && res!=-1;
}

void solve(){
    scanf("%d%d%d",&n,&m,&c);
    MT.init(n);
    int u,v,w,cost;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d",&u,&v,&w,&cost);
        e[i] = edge(u,v,cost,w);
    }
    int l=0,r=1e6+10;
    int mid,ans = -1;
    while(l<=r){
        mid = (l+r)>>1;
        if(check(mid)){
            ans = mid;
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    if(ans <= 0)   puts("impossible");
    else  printf("%d kbps\n",ans);
}
int main(){
    // freopen("1.out","w",stdout);
    int t; scanf("%d",&t);
    for(int i=1;i<=t;++i){
        printf("Case %d: ",i);
        solve();
    }
    return 0;
}

学习博客