hdu 4650 Minimum Average Weight Path(最短、5級)
4951 ワード
第4回多校合同訓練解題報告——詳細は杭電ACM微博を参照~
Minimum Average Weight Path Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 94 Accepted Submission(s): 46 Problem Description In mathematics, a graph is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges. A path in a graph is a sequence of vertices, and for any 2 adjacent u, v, there is a edge from u to v in graph. A path contains at least one edge. In the graph in Sample 2, {3, 3, 2, 2} can form a path from 3 to 2. One of the common problem is to find the shortest path between two certain vertices, or all of them. They've been well studied as the single source shortest path problem (SSSP) and the all pairs shortest paths problem (APSP). In this problem, we'll provide you a derivation analogous to APSP. You've been given a directed graph with positive or negative edge weights. We define the average weight of a path, as the sum of the edge weights divide the edges number of path. Now you need to find the minimum average weight between all pairs of vertices (APMAWP). Input Muiltcases. The first line contains two integer n, m, (1 ≤ n ≤ 102, 1 ≤ m ≤ 104 ) the number of the vertices and the number of the edges. The next m lines, each line contains three intergers u, v, w, representing a directed edge from u to v with weight w. (|w| ≤ 103) There is no multi-edge. It can contain self-loops. Output A n × n matrix representing the APMAWP. The j's element of the i's row represents the minimum average weight of all the paths from vertex i to vertex j. If no such path exists, you need to output "NO"instead (DO NOT output quote please). For each real number, you need to keep exactly 3 digits after digit point. Sample Input
Sample Output
Source 2013 Multi-University Training Contest 5 Recommend zhuyuanchen52
構想:全源は最も短絡して、平均の辺権の最小を求めて、これはやはり比較的に簡単で、その時どうしてこの問題を見に行かなかったのですか?
Minimum Average Weight Path Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 94 Accepted Submission(s): 46 Problem Description In mathematics, a graph is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges. A path in a graph is a sequence of vertices, and for any 2 adjacent u, v, there is a edge from u to v in graph. A path contains at least one edge. In the graph in Sample 2, {3, 3, 2, 2} can form a path from 3 to 2. One of the common problem is to find the shortest path between two certain vertices, or all of them. They've been well studied as the single source shortest path problem (SSSP) and the all pairs shortest paths problem (APSP). In this problem, we'll provide you a derivation analogous to APSP. You've been given a directed graph with positive or negative edge weights. We define the average weight of a path, as the sum of the edge weights divide the edges number of path. Now you need to find the minimum average weight between all pairs of vertices (APMAWP). Input Muiltcases. The first line contains two integer n, m, (1 ≤ n ≤ 102, 1 ≤ m ≤ 104 ) the number of the vertices and the number of the edges. The next m lines, each line contains three intergers u, v, w, representing a directed edge from u to v with weight w. (|w| ≤ 103) There is no multi-edge. It can contain self-loops. Output A n × n matrix representing the APMAWP. The j's element of the i's row represents the minimum average weight of all the paths from vertex i to vertex j. If no such path exists, you need to output "NO"instead (DO NOT output quote please). For each real number, you need to keep exactly 3 digits after digit point. Sample Input
4 4
2 1 2
1 3 -8
2 4 -6
4 3 1
5 8
3 3 735
2 1 946
4 2 276
2 2 -990
3 2 -162
4 4 -18
3 5 783
5 5 -156Sample Output
NO NO -8.000 NO
2.000 NO -3.000 -6.000
NO NO NO NO
NO NO 1.000 NO
NO NO NO NO NO
-990.000 -990.000 NO NO NO
-990.000 -990.000 735.000 NO -156.000
-990.000 -990.000 NO -18.000 NO
NO NO NO NO -156.000Source 2013 Multi-University Training Contest 5 Recommend zhuyuanchen52
構想:全源は最も短絡して、平均の辺権の最小を求めて、これはやはり比較的に簡単で、その時どうしてこの問題を見に行かなかったのですか?
#include<iostream>
#include<cstring>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define clr(f,z) memset(f,z,sizeof(f))
using namespace std;
const int mm=103;
const int oo=0x3f3f3f;
int g[mm][mm],fg[mm][mm],t[mm][mm];
int vis[mm][mm];//
double ans[mm][mm];
int n,m;
void acopy(int(*a)[mm],int(*b)[mm])
{
FOR(i,1,n)FOR(j,1,n)a[i][j]=b[i][j];
}
void mul(int(*a)[mm],int(*b)[mm],int lol)
{ acopy(t,a);FOR(i,1,n)FOR(j,1,n)a[i][j]=oo;
FOR(i,1,n)FOR(j,1,n)FOR(k,1,n)
{
if(vis[i][k]==-1||lol<vis[i][k])continue;
if(vis[k][j]==-1||lol<vis[k][j])continue;
a[i][j]=min(a[i][j],t[i][k]+b[k][j]);
}
}
void debug(int(*a)[mm])
{ puts("+++++++++++++++++++++++");
FOR(i,1,n)FOR(j,1,n)
{
printf("%d ",a[i][j]);
if(j==n)puts("");
}
puts("+++++++++++++++++++++++++");
}
int main()
{ int a,b,c;
while(~scanf("%d%d",&n,&m))
{
FOR(i,1,n)FOR(j,1,n)ans[i][j]=oo;
clr(vis,-1);clr(g,0x3f);
FOR(i,1,m)
{
scanf("%d%d%d",&a,&b,&c);
g[a][b]=c;vis[a][b]=1;
}
FOR(k,1,n)FOR(i,1,n)if(vis[i][k]!=-1)
FOR(j,1,n)if(vis[k][j]!=-1)
{
vis[i][j]=vis[i][j]==-1?vis[i][k]+vis[k][j]:min(vis[i][j],vis[i][k]+vis[k][j]);
}///
acopy(fg,g);
FOR(k,1,n){FOR(i,1,n)FOR(j,1,n)
if(vis[i][j]!=-1&&k>=vis[i][j])///
ans[i][j]=min(ans[i][j],(double)fg[i][j]/k);
mul(fg,g,k);//debug(fg);
}///K
FOR(k,1,n)FOR(i,1,n)if(vis[i][k]!=-1)FOR(j,1,n)
if(vis[k][j]!=-1&&vis[k][k]!=-1)
{
ans[i][j]=min(ans[i][j],ans[k][k]);
}
FOR(i,1,n)FOR(j,1,n)
{
if(j>1)putchar(' ');
if(vis[i][j]==-1)printf("NO");
else //cout<<ans[i][j];
printf("%.3lf",ans[i][j]);
if(j==n)printf("
");
}
}
return 0;
}