這道題其實(shí)就是求去掉某節(jié)點(diǎn)后的最小生成樹的長(zhǎng)度，取最大的長(zhǎng)度的序號(hào)進(jìn)行輸出，如果所有序號(hào)最小生成樹長(zhǎng)度都為0，則輸出0
#include<iostream>#include<vector>#PRagma warning(disable:4996)using namespace std;int N, M, s_max = 0;vector<int> re;int arc[505][505];vector<int> x;vector<int> te;void ins(int t){ for (int i = 1;i <= N;i++) if (i != t) x.push_back(i);}int main(){ for (int t = 0;t < 505;t++) for (int i = 0;i < 505;i++) arc[t][i] = 0x3f3f3f3f; cin >> N >> M; while (M--) { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); if (d) arc[a][b] = arc[b][a] = 0; else arc[a][b] = arc[b][a] = c; } for (int t = 1;t <= N;t++) { x.clear();te.assign(N + 1, -1); ins(t); int f = x.back();x.pop_back(); for (int i = 0;i < x.size();i++)//初始化 te[x[i]] = arc[f][x[i]]; int eff = 0; while (!x.empty())//最小生成樹 { int min_s = 0x3f3f3f3f;int v = 0; for (int i = 0;i < x.size();i++) { if (min_s > te[x[i]]) { min_s = te[x[i]]; v = i; } } if (min_s == 0x3f3f3f3f) { eff = min_s;break; } eff += min_s; int ttt=x[v]; x.erase(x.begin() + v); v = ttt; for (int i = 0;i < x.size();i++) if (arc[v][x[i]] < te[x[i]]) te[x[i]] = arc[v][x[i]]; } if (eff> s_max) { s_max = eff; re.clear(); re.push_back(t); } else if (eff == s_max) re.push_back(t); } if (s_max == 0 && re.size() == N) { cout << 0 << endl;exit(0); } cout << re[0]; for (int t = 1;t < re.size();t++) cout << " " << re[t]; cout << endl;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
