BZOJ1491: [NOI2007]社交网络(Floyd 最短路计数)
2018-07-06 01:19:57来源:博客园 阅读 ()
Submit: 2343 Solved: 1266
[Submit][Status][Discuss]
Description
Input
Output
输出包括n行,每行一个实数,精确到小数点后3位。第i行的实数表示结点i在社交网络中的重要程度。
Sample Input
1 2 1
2 3 1
3 4 1
4 1 1
Sample Output
1.000
1.000
1.000
HINT
社交网络如下图所示。
Source
最短路计数。。
mdzz想到一个做法,应该是$N^3$的,不过与边权有关,然后被卡成$90$分卡成一下午。。
就是直接dfs求最短路计数的时候统计答案,但是不能写记忆化。会wa
// luogu-judger-enable-o2 #include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<map> #include<cmath> using namespace std; const int MAXN = 1e5 + 10, INF = 1e8 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; int dis[101][101], f[101][101], num[101][101][101], w[101][101]; void Floyed() { for(int k = 1; k <= N; k++) { dis[k][k] = 0; for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } } int GetAns(int bg, int now, int pre) { int ans = 0; if(bg == now) return 1; for(int i = 1; i <= N; i++) { if(now != i && dis[bg][now] == dis[bg][i] + w[i][now]) { int x = GetAns(bg, i, pre); num[bg][pre][i] += x; ans += x; } } return ans; } double ans[MAXN]; main() { #ifdef WIN32 freopen("a.in", "r", stdin); //freopen("a.out", "w", stdout); #endif N = read(); M = read(); memset(dis, 0x3f, sizeof(dis)); memset(w, 0x3f, sizeof(w)); for(int i = 1; i <= M; i++) { int x = read(), y = read(), z = read(); w[x][y] = w[y][x] = dis[x][y] = dis[y][x] = z; } Floyed(); for(int i = 1; i <= N; i++) { f[i][i] = 1; for(int j = 1; j <= N; j++) f[i][j] = GetAns(i, j, j); } for(int i = 1; i <= N; i++) { double ans = 0; for(int s = 1; s <= N; s++) { for(int t = 1; t <= N; t++) if(s != i && t != i && s != t) ans += (double)num[s][t][i] / f[s][t]; } printf("%.3lf\n", ans); } return 0; }
标算是Floyd最短路计数,
// luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<map> #include<cmath> #define LL long long using namespace std; const int INF = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; LL dis[101][101], num[101][101]; double ans[101]; void Floyed() { for(int k = 1; k <= N; k++) { for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) { int to = dis[i][k] + dis[k][j]; if(to == INF) continue; if(to < dis[i][j]) dis[i][j] = to, num[i][j] = num[i][k] * num[k][j]; else if(to == dis[i][j]) num[i][j] += num[i][k] * num[k][j]; } } for(int i = 1; i <= N; i++) { for(int s = 1; s <= N; s++) { for(int t = 1; t <= N; t++) { if(s == i || t == i || (dis[s][i] + dis[i][t] != dis[s][t]) || s == t) continue; ans[i] += (double)(1.0 * num[s][i] * num[i][t]) / num[s][t]; } } } } int main() { N = read(); M = read(); for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) dis[i][j] = INF; for(int i = 1; i <= M; i++) { int x = read(), y = read(), z = read(); dis[x][y] = dis[y][x] = z; num[x][y] = num[y][x] = 1; } Floyed(); for(int i = 1; i <= N; i++) printf("%.3lf\n", ans[i]); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ 1188: [HNOI2007]分裂游戏(multi-nim) 2018-06-27
- bzoj1492 [ NOI2007 ] --斜率优化DP+cdq分治 2018-06-17
- bzoj 1185: [HNOI2007]最小矩形覆盖 2018-06-17
- BZOJ 1188: [HNOI2007]分裂游戏(multi-nim) 2018-06-17
- 洛谷P2118 比例简化(暴力) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash