对于 1 号结点而言,只有 2 号到 4 号结点和 4 号到 2 号结点的最短路经过 1 号结点,而 2 号结点和 4 号结点之间的最短路又有 2 条。因而根据定义,1 号结点的重要程度计算为 1/2 + 1/2 = 1 。由于图的对称性,其他三个结点的重要程度也都是 1 。
因为只有 100 个点所以最短路随便乱求都不会有问题... ...
然后用一个二维数组存一下两点的最短路数目,就是一个 DAG 上的 DP... ...
- #include < iostream > #include < cstdio > #include < cstdlib > #include < algorithm > #include < vector > #include < cstring > #include < queue > #include < complex > #include < stack > #define LL long long int#define dob double using namespace std;
- const int N = 110;
- const int M = 10010;
- struct Node {
- int to,
- val,
- next;
- }
- E[M];
- LL head[N],
- tot,
- far[N][N],
- line[N][N];
- int n,
- m,
- deg[N],
- In[N];
- double Ans[N];
- int gi() {
- int x = 0,
- res = 1;
- char ch = getchar();
- while (ch > '9' || ch < '0') {
- if (ch == ' - ') res *= -1;
- ch = getchar();
- }
- while (ch <= '9' && ch >= '0') x = x * 10 + ch - 48,
- ch = getchar();
- return x * res;
- }
- inline void link(int u, int v, int c) {
- E[++tot] = (Node) {
- v,
- c,
- head[u]
- };
- head[u] = tot;
- }
- inline void SPFA(int rt) {
- far[rt][rt] = 0;
- queue < int > Q;
- Q.push(rt);
- while (!Q.empty()) {
- int x = Q.front();
- Q.pop();
- In[x] = 0;
- for (int e = head[x]; e; e = E[e].next) {
- int y = E[e].to;
- if (far[rt][x] + E[e].val < far[rt][y]) {
- far[rt][y] = far[rt][x] + E[e].val;
- if (!In[y]) Q.push(In[y] = y);
- }
- }
- }
- for (int i = 1; i <= n; ++i) for (int e = head[i]; e; e = E[e].next) if (far[rt][E[e].to] == far[rt][i] + E[e].val)++deg[E[e].to];
- line[rt][rt] = 1;
- Q.push(rt);
- while (!Q.empty()) {
- int x = Q.front();
- Q.pop();
- for (int e = head[x]; e; e = E[e].next) {
- int y = E[e].to;
- if (far[rt][x] + E[e].val == far[rt][y]) {
- line[rt][y] += line[rt][x]; --deg[y];
- if (!deg[y]) Q.push(y);
- }
- }
- }
- }
- int main() {
- n = gi();
- m = gi();
- for (int i = 1; i <= m; ++i) {
- int u = gi(),
- v = gi(),
- c = gi();
- link(u, v, c);
- link(v, u, c);
- }
- memset(far, 127 / 3, sizeof(far));
- for (int i = 1; i <= n; ++i) SPFA(i);
- for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) for (int k = 1; k <= n; ++k) if (i != j && i != k && j != k) if (far[i][k] + far[k][j] == far[i][j]) {
- Ans[k] += (double)(line[i][k] * line[k][j]) / (double)(line[i][j]);
- }
- for (int i = 1; i <= n; ++i) printf("%.3lf\n", Ans[i]);
- return 0;
- }