c++ - 以最低成本在城市中 build 街道的算法？

Question

问题详情:
Rashof 是 EMLand 的市长。 EMLand 由十字路口和街道组成。从每个交叉路口到任何其他交叉路口只有一条路径。交点由正整数 1...n 表示。 一家建筑公司提议 Rashof 重建 EMLand 的所有街道，但 Rashof 可以选择最多 k 条街道进行重建。 建筑公司为每条街道提供了一个新的长度，这意味着街道之后是重建后街道长度的变化。 现在作为市长的 Rashof 必须做出明智的选择，以最小化所有十字路口对之间的路径长度总和。 帮助 Rashof!

算法:
符号:旧的边长是L，新的边长是L'，边的集合是E。

1. Count(C) edges(E') 的长度将减少，即 L' < L
   

2. 如果C小于或等于K则
   考虑所有边 (E')，即更新 E 中所有此类边的长度
   

3. 否则
   1.根据 (L'- L) 对所有边 (E') 进行升序排序
   2.根据L'对(L'-L)相同的边(E'' ⊆ E')进行降序排序
   3.选择第一条K条边(E''' ⊆ E') 并更新E中所有这些边的长度

4. 用边E和长度L构造图G

5. 应用任何最短距离算法或 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;
    }

它只通过了 9 个测试用例中的 2 个测试用例。为什么这个算法不起作用？
或者应该对该算法进行哪些修改才能被接受？ 引用:
Rashof, Mayor of EMLand

Answer 1

1. 遍历树/图(例如从任何节点开始的非递归 DFS)并计算每条边的使用次数(一侧的节点数 * 另一侧的节点数)
2. 对于每个可能的重建，将增量乘以计数
3. 排序
4. 利润