地址：

题目：

简单图论问题

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

给出一个无向图，该图由nn个点和mm条边组成，每个点和每条边都有一个权值.

对于该图的任意一个子图，我们定义A是该子图的点权和，B是该子图的边权和，C=A/b=AB是该子图的powerpower值,如果B=0，则C=0。现在，你需要找出该图中具有最大powerpower值的连通的.

其中，图GG的导出子图G′G′满足::

G′G′的点集是GG的点集的子集.

对于GG中的任意一条边，如果该边的两个端点都属于G′G′，那么该边一定属于G′G′.

Input

第一行输入两个整数n,m(1≤n≤500,0≤m≤n∗(n−1)2)n,m(1≤n≤500,0≤m≤n∗(n−1)2),分别表示图的点数和边数.

第二行nn个整数，第ii个数表示标号为ii的点的权值.

接下来mm行，每行三个整数u,v,w(1≤u,v≤n,u≠v,1≤w≤106)u,v,w(1≤u,v≤n,u≠v,1≤w≤106)，表示标号为uu的点和标号为vv的点之间有一条权值为ww的边，保证没有重边和自环.

Output

输出具有最大powerpower值的连通的导出子图的powerpower值，保留两位小数

Sample input and output

Sample Input	Sample Output
3 33 2 11 2 51 3 42 3 4	1.00

Source

每周一题 Div2

　　

　思路：仔细思考下会发现只选一条边是最优的，所以选最大权值的边即可。

1 #include 
        
          2  3 using namespace std; 4  5 #define MP make_pair 6 #define PB push_back 7 typedef long long LL; 8 typedef pair
         
           PII; 9 const double eps=1e-8;10 const double pi=acos(-1.0);11 const int K=1e6+7;12 const int mod=1e9+7;13 14 int n,m,v[K];15 double ans;16 int main(void)17 {18     scanf("%d%d",&n,&m);19     for(int i=1;i<=n;i++)20         scanf("%d",v+i);21     for(int i=1,x,y,w;i<=m;i++)22     {23         scanf("%d%d%d",&x,&y,&w);24         if(w)25             ans=max(ans,(v[x]+v[y])*1.0/w);26     }27     printf("%.2f\n",ans);28     return 0;29 }