HDU 4081 MST
这道题在LRJ的书上看到,今天回过头来继续看这题,发现很多东西都已经明白了。题意:有N个城市,每个城市有一个坐标和人口。
现在要建一些边使得他们都联通,花费就是这些边的长度,然后有一条边可以免费。问免费一条边之后,使得免费的该条边的两个城市的人口/剩下来的边的长度 ,这个比值最大。
思路:首先做一遍MST,求出MST之后,我们枚举每条边,看这条边是否可以删除,也就是免费。
那么删除一条边之后对MST有什么影响呢。
首先我们假设免费(删除)了一条边a -> b ,权值是c 。假设这条边是MST上的边,那么我们只能删除这条边 。
假设这条边不是MST上的边,那么我们可以删除a -> b权值最大的一条边,因为我们是要使得剩下来的长度最小。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <stack> #include <set> #include <map> #include <queue> #include <algorithm> #define ll long long #define inf 1<<30 #define PI acos(-1.0) #define mem(a , b) memset(a , b ,sizeof(a)) using namespace std ; struct kdq { int s , e ; double l ; bool operator < (const kdq & fk)const { return l > fk.l ; } } ; inline void RD(int &ret) { char c; int flag = 1 ; do { c = getchar(); if(c == '-')flag = -1 ; } while(c < '0' || c > '9') ; ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); ret *= flag ; } #define N 1111 double ed[N][N] , edM[N][N] ; int x[N] , y[N], pop[N] ; int n ; double mst = 0 ; double getdis(int i ,int j) { return sqrt(1.0 * (x[i] - x[j]) * (x[i] - x[j]) + 1.0 * (y[i] - y[j]) * (y[i] - y[j])) ; } void init() { cin >> n ; for (int i = 1; i <= n ; i ++ ) { RD(x[i]) ; RD(y[i]) ; RD(pop[i]) ; } for (int i = 1 ; i <= n ; i ++ ) { for (int j = 1; j <= n ; j ++ ) { if(i == j)ed[i][j] = 0 ; else ed[i][j] = getdis(i , j) ; } } mst = 0 ; } double dis[N] ; int vis[N] ; bool ok[N][N] ; vector<int>E[N] ; void prim() { priority_queue<kdq>qe ; for (int i = 1 ; i <= n ; i ++ ) { dis[i] = ed[1][i] ; E[i].clear() ; } mem(vis ,0) ; mem(ok ,0) ; for (int i = 1 ; i <= n ; i ++ ) { qe.push((kdq) {1 , i , ed[1][i]}) ; } dis[1] = 0 , vis[1] = 1 ; while(!qe.empty()) { kdq tp = qe.top() ; qe.pop() ; if(vis[tp.e])continue ; mst += ed[tp.s][tp.e] ; vis[tp.e] = 1 ; ok[tp.s][tp.e] = ok[tp.e][tp.s] = 1 ; E[tp.s].push_back(tp.e) ; E[tp.e].push_back(tp.s) ; for (int i = 1 ; i <= n ; i ++ ) { if(!vis[i] && dis[i] > ed[tp.e][i]) { dis[i] = ed[tp.e][i] ; qe.push((kdq){tp.e , i , ed[tp.e][i]}) ; } } } } void dfs(int root ,int fa ,int now ,double MAX) { edM[root][now] = MAX ; int sz = E[now].size() ; for (int i = 0 ; i < sz ; i ++ ) { int e = E[now][i] ; if(e == fa)continue ; dfs(root , now , e , max(MAX , ed[now][e])) ; } } void solve() { init() ; prim() ; for (int i = 1 ; i <= n ; i ++ ) { dfs(i , -1 , i , 0) ; } double ans = -1 ; for (int i = 1 ; i <= n ; i ++ ) { for (int j = 1 ; j < i ; j ++ ) { if(ok[i][j]) ans = max(ans , (pop[i] + pop[j]) * 1.0 / (mst - ed[i][j])) ; else ans = max(ans , (pop[i] + pop[j]) * 1.0 / (mst - edM[i][j])) ; } } printf("%.2f\n",ans) ; } int main() { int _ ;cin >> _ ;while(_ -- )solve() ; return 0; }
补充:软件开发 , C++ ,