以最小成本建造城市街道的算法？

Question

问题详情:
拉绍夫是埃姆兰市市长。埃姆兰由十字路口和街道组成。从每个交叉口到任何其他交叉口都只有一条路径。交点用正整数1...n表示。一家建筑公司向Rashof提出要重建埃姆兰的所有街道，但Rashof最多可以选择k条进行重建。建筑公司为每条街道提供了一个新的长度，这意味着在街道重建后，街道的长度会发生变化。现在，作为城市的市长，拉绍夫必须明智地做出选择，使所有对交叉口之间的路径长度之和最小化。救救Rashof！

算法:
符号：旧边长为L，新边长为L'和边集E。

>

计数(c)长度将减小的边(E')的数目，即L'

如果C小于或等于K则
 、 、 、 、 、 、 、 将所有边(E')考虑在内，即更新E中所有这些边的长度

其他
       1.基于(L'-L)的所有边(E')按升序排序
         2。根据L'降序排序那些(L'-L)相同的边(E''E')
         3.后K条边(E'''E')并更新E中所有这些边的长度

构造边为E、长度为L的图G

应用任何最短距离算法或DFS来寻找每对节点的距离B/W。

使用优先级队列和Dijkstra算法实现上述算法。

    #include <bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> pii;
    struct s{
    int x;
    int y;
    int a;
    int b;
    int c;
    };
    const int MAX = 100000;
    const long long INF = 100000000000000000;
    vector< pii > G[MAX];
    long long d[MAX];
    void dijkstra(long long start) {
        int u, v, i, c, w;
        priority_queue< pii, vector< pii >, greater< pii > > Q;
        for(i=0;i<MAX;i++){
            d[i]=INF;
        }
        Q.push(pii(0, start));
        d[start] = 0;
        while(!Q.empty()) {
            u = Q.top().second; // node
            c = Q.top().first; // node cost so far
            Q.pop(); // remove the top item.
            if(d[u] < c) continue;
            for(i = 0; i < G[u].size(); i++) {
                v = G[u][i].first; // node
                w = G[u][i].second; // edge weight
                if(d[v] > d[u] + w) {
                    d[v] = d[u] + w;
                    //cout<<d[v];
                    Q.push(pii(d[v], v));
                }
            }
        }
    }
    bool func(const s s1,const s s2) { return (s1.c < s2.c); }
    bool func2(const s s1,const s s2) { return (s1.b < s2.b); }
    int main() {
        long long n, e, u, V, w,x,y,a,b,t,i,j,k,res,z=2;
        s S;
        vector<s> v;
        map<pair<int,int>,int> m;
        map<pair<int,int>,int>::iterator it;
        cin>>t;
        while(t--){
            cin>>n>>k;
            for(i = 1; i <= n; i++) G[i].clear();
            v.clear();
            m.clear();
            for(i=1;i<n;i++){
                cin>>x>>y>>a>>b;
                if(b<a){
                    S.x = x;
                    S.y =y;
                    S.a=a;
                    S.b=b;
                    S.c=b-a;
                    v.push_back(S);
                }
                m[make_pair(x,y)]=a;
            }
            if(v.size()<=k){
                for(i=0;i<v.size();i++){
                     m[make_pair(v[i].x,v[i].y)]=v[i].b;
                }
                it = m.begin();
                for(;it!=m.end();++it){
                    u = it->first.first;
                    V = it->first.second;
                    w = it->second;
                    G[u].push_back(pii(V, w));
                    G[V].push_back(pii(u, w));
                }
                res = 0;
                for(i=1;i<=n;i++){
                    dijkstra(i);
                    for(j= 1; j <= n; j++) {
                        if(i == j) continue;
                        if(d[j] >= INF) ;
                        else res+=d[j];
                    }
                }
                cout<<res/z<<"\n";
            }
            else{
                sort(v.begin(),v.end(),func);
                for(i=0;i<v.size();i++){
                    j = i;
                    while(v[i].c==v[j].c&&j<v.size())j++;
                    sort(v.begin()+i,v.begin()+j,func2);
                    i=j;
                }
                for(i=0;i<k;i++){
                     m[make_pair(v[i].x,v[i].y)]=v[i].b;
                }
                it = m.begin();
                for(;it!=m.end();++it){
                    u = it->first.first;
                    V = it->first.second;
                    w = it->second;
                    G[u].push_back(pii(V, w));
                    G[V].push_back(pii(u, w));
                }
                res = 0;
                for(i=1;i<=n;i++){
                    dijkstra(i);
                    for(j= 1; j <= n; j++) {
                        if(i == j) continue;
                        if(d[j] >= INF) ;
                        else res+=d[j];
                    }
                }
                cout<<res/z<<"\n";
            }
        }
        return 0;
    }

Answer 1

注意，这是一棵树，所以，每条边连接两个相连的组件。

假设我们在两个连通分量A和B之间有边连通，其中包含n和m个交点，因此，通过减小边的x个单位，我们将减小总距离n*m*x。

A---B---C----E
    |   |
    |   |
D----   -----F

看上图,B和C之间的边连接两个连通的分量（A,B,D）和（C,E,F）,减小这条边的权值将减小（A,B,D）和（C,E,F）之间的距离

因此，算法是选择k条边，该边具有最大的n*m*x（如果x为正）。