程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4081 Qin Shi Huang's National Road System(最小生成樹/次小生成樹)

HDU 4081 Qin Shi Huang's National Road System(最小生成樹/次小生成樹)

編輯:C++入門知識

HDU 4081 Qin Shi Huang's National Road System(最小生成樹/次小生成樹)


 

題意:

有n坐城市,知道每坐城市的坐標和人口。現在要在所有城市之間修路,保證每個城市都能相連,並且保證A/B 最大,所有路徑的花費和最小,A是某條路i兩端城市人口的和,B表示除路i以外所有路的花費的和(路徑i的花費為0).

分析:

先求一棵最小生成樹,然後枚舉每一條最小生成樹上的邊,刪掉後變成兩個生成樹,然後找兩個集合中點權最大的兩

個連接起來。這兩個點中必然有權值最大的那個點,所以直接從權值最大的點開始dfs。

  為了使A/B的值最大,則A盡可能大,B盡可能小。所以B中的邊一定是MST上去掉一條邊後的剩余所有邊。首先用O(N^2)算出

  MST,然後依次枚舉,刪去MST上的每一條邊,MST變成兩棵樹T1和T2,然後在剩余的邊(即不在MST上的邊),以及這條刪

  去的邊中找到該邊的兩點的權值和最大以及能夠連接T1和T2的邊,A=刪去邊後的替換邊的兩點的權值和,B=刪去該邊後的MST

  的值,求A/B最大。則A盡可能大,A分別是T1和T2中最大的兩個點,則所有點中權值最大的點一定在A中,由此在MST上從權值

  最大的點作為root,開始dfs。遞歸求出子樹中的每個最大的點以及求出A/B的比值,求出最大。

分析轉載自:傳送門

我的理解,首先很明顯我們是需要求出最小生成樹的,然後我們可以枚舉邊(u,v)中的邊,很明顯枚舉的邊都會

與原來MST中的邊形成一個環,因為這個邊不在MST中,那麼這個邊的權值一定是大於MST中連接U,V的邊的,因此

我們在這個環裡去掉的應該是權值最大的邊。

代碼如下:

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 1e3+10;

const int inf = 1e9+10;

struct point{
    int x,y;
}a[maxn];

int head[maxn],par[maxn],peo[maxn];

bool vis[maxn];

int ip,mmax;
double ans ,mst;

struct tree{
    int u,v;
    double w;
    tree(){}
    tree(int _u,int _v,double _w):u(_u),v(_v),w(_w){}
    bool operator < (const struct tree &tmp)const{
        return wmmax){
                mmax=peo[i];
                root=i;
            }
        }
        int cnt = 0;
        for(int i=0;i

 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved