7-38 最小生成树的唯一性

输入样例 1：

5 7
1 2 6
5 1 1
2 3 4
3 4 3
4 1 7
2 4 2
4 5 5

输出样例 1：

11
Yes

输入样例 2：

4 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

输出样例 2：

4
No

输入样例 3：

5 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3

输出样例 3：

No MST
2

C/C++ 

box[a] -> 节点 a '直接连接的所有通路'

apr -> appear

#include
using namespace std;
long road[501][501];
vector<int> box[501];
bool apr[501];
void BFS(int now);
pair<long,bool>Prim(int N);
int main()
{
    memset(road,0x6f,sizeof road);
    int N,M,flag=0,a,b,c;
    cin >> N >> M;
    while (M--){
        cin >> a >> b >> c;
        box[a].push_back(b);
        box[b].push_back(a);
        road[a][b] = road[b][a] = c;
//        cout << road[a][b] << " " << road[b][a] << endl;
    }
 
    for(int z=1;z<=N;z++) if(!apr[z]) {
            flag++;
            BFS(z);
        }
 
    if(flag>1) cout << "No MST" << endl << flag << endl;
    else
    {
        pair<long,bool> x = Prim(N);
        cout << x.first << endl << (x.second?"Yes":"No");
    }
 
    return 0;
}
void BFS(int now){
    if(apr[now]) return;
    apr[now] = true;
    for(int x:box[now]) BFS(x);
}
 
 
pair<long,bool>Prim(int N){
    long ed[501];
    memset(apr,0,sizeof apr);
    memset(ed,0x6f,sizeof ed);
    bool flag = true;
    long sum = ed[1] = 0,f[501],len=0;
    vector<int> ops;
    for(int z=1;z<=N;z++){
        int op = -1;
        for(int z1=1;z1<=N;z1++){
            if(!apr[z1]){
                if(op==-1 || ed[z1]0;
                if(op==-1 || ed[z1]<=ed[op]) f[len++] = z1;
            }
        }
 
        if(flag) {
            for(int z1=0;z1
                int num = 0;
                for(int z2:ops) if(road[z2][f[z1]]==ed[op] && apr[z2]) num++;
                if(num>1) flag = false;
                for(int z2=z1+1;z2
                    if(road[f[z1]][f[z2]]<=ed[op]) flag = false;
                    if(!flag) break;
                }
            }
 
 
        }
 
        apr[op] = true;
        ops.push_back(op);
        sum += ed[op];
 
        for(int z1=1;z1<=N;z1++) ed[z1] = min(ed[z1],road[op][z1]);
    }
 
    return {sum,flag};
}