제목: n (n = 1000) 개의 2 차원 점 을 드 리 겠 습 니 다. 첫 번 째 점 은 power plant 이 고 n - 1 점 은 dormitories 입 니 다.그리고 지금 은 침실 이 침실 옆 에 연결 되 지 않 는 다 는 것 을 알 고 있 습 니 다. 그러나 우 리 는 어느 쪽 인지 모 릅 니 다. 이런 상황 에서 최소 생 성 나무의 최대 치 를 물 었 습 니 다.
사고: 아주 소박 한 알고리즘 은 삭 제 된 모든 변 을 매 거 진 다음 에 최소 생 성 트 리 를 만 드 는 것 이다. 복잡 도가 높 은 하늘 을 돌파 하 는 것 은 분명 안 된다.
그러나 위 에 있 는 그런 방법 을 생각 한 이상 다시 생각해 보면 얻 을 수 있 습 니 다. 우 리 는 삭 제 된 모든 변 을 매 거 합 니 다. 다만 이 변 은 나무 변 이기 때문에 관건 은 이 변 을 삭제 한 그림 의 최소 생 성 트 리 와 원래 의 최소 생 성 트 리 의 관 계 를 삭제 하 는 것 입 니 다.
우 리 는 먼저 MINE [i] [j] 를 미리 처리 하여 점 i 에서 점 j 의 가장 짧 은 한 변 을 표시 할 수 있다.그리고 NMIN [i] [j] 를 미리 처리 하여 변 i - > j 를 제거 한 후 i - > j 의 가장 짧 은 변 을 표시 합 니 다.
그럼 한 변 의 증 가 를 빼 면 NMIN [i] [j] - MINE [i] [j] 입 니 다.그리고 최대 치 를 취하 면 됩 니 다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
using namespace std;
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
#define M 111111
int st[M] ;
int top ;
double NMIN[N][N] ;
int x[N] , y[N] , cost , n ;
double Map[N][N] ;
double dis[N] ;
bool vis[N] ;
vectorG[N] ;
priority_queueqe ;
double mst = 0 ;
bool ismst[N][N] ;
double MINE[N][N] ;
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])) ;
}
struct kdq{
int s , e ;
double l ;
bool operator < (const kdq & fk)const {
return l > fk.l ;
}
} ;
void Prim(){
mst = 0 ;
mem(ismst, 0) ;
while(!qe.empty())qe.pop() ;
for (int i = 0 ; i < n ; i ++ )dis[i] = Map[0][i] , vis[i] = 0 ,G[i].clear() ,qe.push((kdq){0 , i , dis[i]}) ;
dis[0] = 0 , vis[0] = 1 ;
while(!qe.empty()){
kdq tp = qe.top() ; qe.pop() ;
if(vis[tp.e])continue ;
mst += Map[tp.s][tp.e] ;
vis[tp.e] = 1 ;
G[tp.s].push_back(tp.e) ; G[tp.e].push_back(tp.s) ;
ismst[tp.e][tp.s] = ismst[tp.s][tp.e] = 1 ;
MINE[tp.s][tp.e] = MINE[tp.e][tp.s] = inf ;//
for (int i = 0 ; i < n ; i ++ )if(!vis[i] && dis[i] > Map[tp.e][i])dis[i] = Map[tp.e][i] , qe.push((kdq){tp.e , i , dis[i]}) ;
}
}
void dfs(int root , int fa , int now){
int sz = G[now].size() ;
for (int i = 0 ; i < sz ; i ++ ){
int e = G[now][i] ;
if(e != fa)dfs(root , now , e) , MINE[root][now] = min(MINE[root][now] , MINE[root][e]) ;
}
}
void dfs(int fa, int now){
int fk = top ;
st[ ++ top] = now ;int sz = G[now].size() ;
for (int i = 0 ; i < sz ; i ++ ){
int e = G[now][i] ; if(e != fa)dfs(now , e) ;
}
if(fa != -1){
NMIN[now][fa] = NMIN[fa][now] = inf ;
for (int i = fk + 1 ; i <= top ; i ++ )NMIN[now][fa] = NMIN[fa][now] = min(NMIN[fa][now] , MINE[st[i]][fa]) ;
}
}
void solve(){
cin >> n >> cost ;
for (int i = 0 ; i < n ; i ++ )RD(x[i]) , RD(y[i]) ;
for (int i = 0 ; i < n ; i ++ )
for (int j = 0 ; j < n ; j ++ )
MINE[i][j] = Map[i][j] = (i == j) ? 0 : getdis(i , j) ;
Prim() ;
for (int i = 0 ; i < n ; i ++ )dfs(i , -1 , i ) ;
top = 0 ;
dfs(-1 , 0) ;
double ans = 0 ;
for (int i = 0 ; i < n ; i ++ ){
for (int j = 0 ; j < n ; j ++ ){
if(i == 0 || j == 0)continue ;
if(!ismst[i][j])continue ;
ans = max(ans , NMIN[i][j] - Map[i][j]) ;
}
}
printf("%.2f
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[알고리즘] Java / 백준 / 도시 분할 계획 / 1647
[알고리즘] Java / 백준 / 도시 분할 계획 / 1647
문제
접근 방식
최소 스패닝 트리를 구하면서 트리를 구성하는 간선 비용의 합을 구한 후 여기에 간선의 최댓값을 빼면 두 마을을 분리하는 길의 유지비 최솟...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
