不太懂我这个方法错在了哪里
查看原帖
不太懂我这个方法错在了哪里
819682
Exile_Code楼主2024/3/22 17:19
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <math.h>
#include <functional>



#define ull		        unsigned long long 
#define ll              long long
#define pii             pair<ll ,ll>
#define cy              cout<<"YES"<<endl
#define cn              cout<<"NO"<<endl
#define forn(i,begin,end,add)	for(ll (i)=(begin);(i)<=(end);(i)+=(add))	//begin是i的起始,end是i的终止,add是每次加的大小
#define rforn(i,begin,end,sub)  for(ll (i)=(end);(i)>=(begin);(i)-=(sub))	//r是倒序遍历
#define vv              vector
#define inf32           INT32_MAX/2
#define inf64           INT64_MAX/2
#define LD              double
#define PI              acos(-1)
#define debug(a,b)		cout<<a<<b
#define eps				1e-12


const int N = 4e5 + 100;
const int mod = 998244353;
ll T;

int n;
vv<vv<pii>>tree;
vv<ll>d1;
vv<ll>d2;
vv<ll>w;
int bfs(int x,vv<ll>&d) {
    vv<int>flag(n+2);
    queue<int>q;
    q.push(x);
    while (q.size()) {
        int floor = q.size();
        while (floor--) {
            int nd = q.front();     flag[nd] = 1;   q.pop();
            for(auto a:tree[nd]) {
                if (!flag[a.first])
                    q.push(a.first), d[a.first] = d[nd] + a.second;
            }
        }
    }
    ll mx = 0;
    forn(i, 1, n, 1) {
        if (d[i] > d[mx])
            mx = i;
    }
    return mx;
}
void solve() {

    ll ans = 0;
    cin >> n;
    
   tree.resize(n + 1);  d1.resize(n + 1);d2.resize(n + 1);
    forn(i, 1, n - 1, 1) {
        int a, b; cin >> a >> b;
        int c; cin >> c;
        tree[b].push_back({ a,c });
        tree[a].push_back({ b,c });
    }
            
    vv<ll>d3(n + 1);
    int nd = bfs(1, d1);
    int mx = bfs(nd, d2);
    bfs(mx, d3);

    //找两条直径的四个端点
    int mx1 = -1, mx2 = -1;
    int nd1 = -1 , nd2 = -1;
    
    forn(i, 1, n, 1) {
        if (d2[i] == d2[mx]) {
            if (mx1 == -1){
                mx1 = i; continue;
            }
            if (mx1 && nd2 == -1) {
                mx2 = i;  break;
            }
        }
    }
    forn(i, 1, n, 1){
        if (d3[i] == d2[mx]){
            if (nd1 == -1)  {
                nd1 = i;   continue;
            }
            if (nd1 && nd2 == -1){
                nd2 = i;    break;
            }
        }
    }
    if (nd2 == -1)
        nd2 = nd1;
    if (mx2 == -1)
        mx2 = mx1;

    ll len = d2[mx];//直径长度

    vv<ll>dd1(n + 1);vv<ll>dd2(n + 1);vv<ll>dd3(n + 1);vv<ll>dd4(n + 1);
    bfs(nd1, dd1);bfs(nd2, dd2); bfs(mx1, dd3);bfs(mx2, dd4);
    //如果一个点到这四个端点的距离相同,则在公共直径上
    forn(i, 1, n, 1) {
        ll len1 = dd1[i] + dd3[i];  ll len2 = dd2[i] + dd4[i];
        if (len1 == len && len == len2)  ans++;
    }
    cout << len << endl;
    cout << ans - 1 << endl;

}
int main() {

    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    T = 1;
   // cin >> T;
    while (T--)
        solve();
    return 0;

}


2024/3/22 17:19
加载中...