网站 › 『编程语言讨论求助区』 › 算法求助

yfjhhh 发表于 2023-6-26 20:52

算法求助

求助，自己写的一个最小生成树代码，AC不了
洛谷题目
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
struct edge{ //定义边
      int value;//权值
      int spot;//到达点
};
bool spot;//点是否经过
struct cmp {
      bool operator() (edge& a,edge& b) {
                // 定义优先级的比较方式
                return a.value < a.value;
      }
};
priority_queue<edge, vector<edge>, cmp> pq;
int main()
{
      int map;
      edge e;
      memset(map,-1,sizeof(map));
      int n,m;
      cin>>n>>m;
      for(int i=1;i<=m;i++){
                int x,y,z;
                cin>>x>>y>>z;
                map=z;
                map=z;
                //cout<<z<<endl;
      }
      int begin=1,l=0,ans=0;
      do{
                //cout<<111<<endl;
                for(int i=1;i<=n;i++){
                        //cout<<"test1:"<<i<<endl;
                        if(map!=-1&&spot==0){
                              e.spot=i;
                              e.value=map;
                              pq.push(e);
                              //cout<<"test2:"<<begin<<"to"<<e.spot<<endl;
                        }
                }
                spot=1;
                if(!pq.empty()&&l<=n-2){
                        edge eee;
                        eee=pq.top();
                        ans+=eee.value;
                        begin=eee.spot;
                        l++;
                        //cout<<"test3:"<<ans<<endl;
                        pq.pop();
                }
                else
                {
                        break;
                }
      }while(1);
      //cout<<ans<<endl;
      //cout<<l<<endl;
      //cout<<l<<endl<<n;
      if(l==n-1){
                cout<<ans;
      }
      else
      {
                cout<<"orz";
      }
}
```

yfjhhh 发表于 2023-6-26 21:17

链接https://www.luogu.com.cn/problem/P3366#submit

TenSir152 发表于 2023-6-27 07:00

我先去实验一下

400h297004533 发表于 2023-6-27 19:39

#include<bits/stdc++.h>
using namespace std;

struct edge {
    int value; // 权值
    int spot;// 到达点
};

bool spot;// 点是否经过

struct cmp {
    bool operator() (edge& a, edge& b) {
      // 定义优先级的比较方式
      return a.value < b.value;
    }
};

priority_queue<edge, vector<edge>, cmp> pq;

int main() {
    int map;
    edge e;
    memset(map, 0, sizeof(map));
   
    int n, m;
    cin >> n >> m;
   
    for (int i = 1; i <= m; i++) {
      int x, y, z;
      cin >> x >> y >> z;
      map = z;
      map = z;
    }
   
    int begin = 1, l = 0, ans = 0;
   
    do {
      for (int i = 1; i <= n; i++) {
            if (map != 0 && spot == 0) {
                e.spot = i;
                e.value = map;
                pq.push(e);
            }
      }
      
      spot = 1;
      
      if (!pq.empty() && l <= n - 2) {
            edge eee = pq.top();
            ans += eee.value;
            begin = eee.spot;
            l++;
            pq.pop();
      } else {
            break;
      }
    } while (1);
   
    if (l == n - 1 && pq.empty()) {
      cout << ans;
    } else {
      cout << "orz";
    }
   
    return 0;
}

查看完整版本: 算法求助