(UVA) 10600 - ACM Contest and Blackout [次小生成樹---Prim，LCA]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=1541

這題簡單來講，是求 "次小生成樹" 。

那，就是先把MST找出來，之後每找一個邊 (注意有重邊！！！)，試著帶帶看。

那，求的過程中，我們需要LCA(lowest common ancestor)幫助！

用Kruskal求次小MST

我是用Prim求MST

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <utility>
#include <cmath>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 103;
const int MAX_P = 11;  //MAX_P = log(MAX_N)
const int INF = 1e9+7;

bool visit[MAX_N];
int d[MAX_N];
int parent[MAX_N];
int w1[MAX_N][MAX_N];
int w2[MAX_N][MAX_N];
int depth[MAX_N];
int binary[MAX_P];
pii lca[MAX_P][MAX_N];

void init() {
 for (int x=0;MAX_N>x;x++) {
  for (int y=0;MAX_N>y;y++) {
   w1[x][y] = w2[x][y] = INF;
  }
 }
}

int Prim(int n) {
 int sum=0;
 
 for (int x=1;n>=x;x++) {
  d[x]=INF;
  visit[x]=false;
 }
 
 parent[1]=1;
 d[1]=0;
 depth[1]=0;
 
 for (int x=0;n>x;x++) {
//  cout<<"x="<<x<<" , sum="<<sum<<endl;
  int p,min=INF;
  for (int y=1;n>=y;y++) {
   if (!visit[y] && d[y] < min) {
    min=d[y];
    p=y;
   }
  }
  if (p!=parent[p])sum += w1[p][parent[p]];
  visit[p]=true;
  depth[p] = depth[parent[p]] + 1;
  
  for (int y=1;n>=y;y++) {
   if (!visit[y] && d[y] > w1[p][y]) {
    d[y]=w1[p][y];
    parent[y]=p;
   }
  }
 }
 return sum;
}

void LCA(int n) {
 for (int x=0;MAX_P>x;x++) {
  for (int y=1;n>=y;y++) {
   if (y==1) lca[x][y] = make_pair(y,0);
   else if (x==0)lca[x][y] = make_pair(y,0);
   else if (x==1) lca[x][y] = make_pair(parent[y],w1[y][parent[y]]);
   else lca[x][y] = make_pair(lca[x-1][lca[x-1][y].first].first,max(lca[x-1][y].second,lca[x-1][lca[x-1][y].first].second));
  }
 }
}

pii walk(int x,int depth) {
// cout<<"walk : "<<x<<" , "<<depth;
 memset(binary,0,sizeof(binary));
 int id=1;
 int tmp=depth;
 while (tmp>0) {
  binary[id++] = tmp%2;
  tmp/=2;
 }
 int mx=0;
 for (int i=1;id>i;i++) {
  if (binary[i]==1) {
   mx = max(mx,lca[i][x].second);
   x = lca[i][x].first;
  }
 }
// cout << "  :  "<<x<<" , "<<mx<<endl;
 return make_pair(x,mx);
}

int Find(int x,int y) {
 int L=1,R=min(depth[x],depth[y])+1;
 while (R-L!=1) {
//  cout<<L<<" ~ "<<R<<endl;
  int mid=(L+R)>>1;
  if (walk(x,depth[x]-mid).first == walk(y,depth[y]-mid).first) L=mid;
  else R=mid;
 }
// cout<<"L="<<L<<endl;
 return max(walk(x,depth[x]-L).second,walk(y,depth[y]-L).second);
}

int main () {
// freopen("output.txt","w",stdout);
 int T;
 scanf("%d",&T);
 while (T--) {
  init();
  int n,m;
  scanf("%d %d",&n,&m);
  for (int x=0;m>x;x++) {
   int a,b,c;
   scanf("%d %d %d",&a,&b,&c);
   if (w1[a][b] == INF) {
    w1[a][b] = c;
    w1[b][a] = c;
   }
   else {
    int tmp=w1[a][b];
    w1[a][b] = min(w1[a][b],c);
    tmp=max(tmp,c);
    w2[a][b] = min(w2[a][b],tmp);
    w1[b][a] = w1[a][b];
    w2[b][a] = w2[a][b];
//    cout<<"GETTTT   "<<w1[a][b] << ' '<<w2[a][b]<<endl;
   }
  }
  int sum=Prim(n);
//  for (int x=1;n>=x;x++) cout<<parent[x] << ' ';
//  cout<<endl;
//  for (int x=1;n>=x;x++) cout<<depth[x]<<' ';
//  cout<<endl;
  LCA(n);
//  for (int x=0;4>x;x++) {
//   for (int y=1;n>=y;y++) {
//    cout<<lca[x][y].first<< ","<<lca[x][y].second<<" ";
//   }
//   cout<<endl;
//  }
  int ans2=INF;
//  cout<<Find(5,3)<<endl;
  for (int i=1;n>=i;i++) {
   for (int j=1;n>=j;j++) {
    if (i==j) continue;
    if (parent[i]==j || parent[j]==i) {  //重邊 
//     cout<<"i = "<<i<<" , j="<<j<<", new="<<sum+w2[i][j] - w1[i][j]<<endl;
     if (w2[i][j] != INF) {
      ans2 = min(ans2,sum+w2[i][j] - w1[i][j]);
     }
    }
    else if (w1[i][j] != INF) {
     int ret=Find(i,j);
//     cout<<"i="<<i<<" , j="<<j<<" ret = "<<ret<<" , new = "<<sum+w1[i][j] - ret<<endl;
     ans2 = min(ans2,sum+w1[i][j] - ret);
    }
   }
  }
  printf("%d %d\n",sum,ans2);
 }
}