hoj12616 Median Tree ——最小生成树入门题&&比赛残留题_Kruscal算法

May 1, 2013
Graph

题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=12616 题目大意：　　给n个点,m条边，求一棵生成树，使得这个生成树的边的权值的中位数最小。输出这个中位数。题目思路：　　和poj1861&&zoj1542的思路是一样的。可以证明要求的树就是最小生成树。然后就是中位数的概念：长度为N的数列的中位数，就是(N+1)/2位置的数字。百度百科里面貌似不是严格的中位数的概念。　　开始写了一遍按照那种不严格的中位数的定义写的。过了。kruscal的过程中，只需要计算到(n-1+1)/2-1的那一条边即可退出。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
int n, m;
const int em = 10000+10, vm = 1000+10;
typedef struct Edge {
  int u, v, w;
  bool operator < (const Edge &other) const {
    return w < other.w;
  }
}Edge;
Edge edge[em];
int parent[vm];
void init()
{
  for (int i = 1; i <= n; ++i) parent[i] = -1;
}
int Find(int x)
{
  int s;
  for (s = x; parent[s] >= 0; s = parent[s]) ;
  while (s != x) {
    int tmp = parent[x]; parent[x] = s; x = tmp;
  }
  return s;
}
void Union(int R1, int R2)
{
  int r1 = Find(R1), r2 = Find(R2), tmp = parent[r1] + parent[r2];
  if (parent[r1] > parent[r2]) {
    parent[r1] = r2; parent[r2] = tmp;
  } else {
    parent[r2] = r1; parent[r1] = tmp;
  }
}
void kruscal()
{
  init();
  int i, j, res, u, v, w, cnt = 0;
  for (i = 0; i < m; ++i) {
    u = edge[i].u; v = edge[i].v; w = edge[i].w;
    if (Find(u) != Find(v)) {
      res = w; Union(u, v);
      if (cnt == (n)/2 - 1) {
        printf("%d\n", res); break;
      }
      cnt++;
    }
  }
}

int main(void){
#ifndef ONLINE_JUDGE
  freopen("hoj12616.in", "r", stdin);
#endif
  int i, j;
  while (~scanf("%d%d", &n, &m) && (m||n)) {
    for (i = 0; i < m; ++i) {
      scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    }
    sort(edge, edge + m);
    kruscal();
  }

  return 0;
}

　　然后又修改了一下，根据严格的中位数的定义。在kruscal的过程中，计算出中间的两个数字的和，然后取平均值，输出。也过了……


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
int n, m;
const int em = 10000+10, vm = 1000+10;
typedef struct Edge {
  int u, v, w;
  bool operator < (const Edge &other) const {
    return w < other.w;
  }
}Edge;
Edge edge[em];
int parent[vm];
void init()
{
  for (int i = 1; i <= n; ++i) parent[i] = -1;
}
int Find(int x)
{
  int s;
  for (s = x; parent[s] >= 0; s = parent[s]) ;
  while (s != x) {
    int tmp = parent[x]; parent[x] = s; x = tmp;
  }
  return s;
}
void Union(int R1, int R2)
{
  int r1 = Find(R1), r2 = Find(R2), tmp = parent[r1] + parent[r2];
  if (parent[r1] > parent[r2]) {
    parent[r1] = r2; parent[r2] = tmp;
  } else {
    parent[r2] = r1; parent[r1] = tmp;
  }
}
void kruscal()
{
  init();
  int i, j, res, u, v, w, cnt = 0, od;
  bool flag = false;
  for (i = 0; i < m; ++i) {
    u = edge[i].u; v = edge[i].v; w = edge[i].w;
    if (Find(u) != Find(v)) {
      res = w; Union(u, v);
      if (((n-1)&1==0) && (cnt ==(n-1)/2)) {
        od = w;
      }
      else if ( ((n-1)&1==0) && (cnt==(n-1)/2+1) ) {
        printf("%d\n", (od + res) / 2 ); break;
      }
      else if (((n-1)&1)&& (cnt==(n)/2-1)) {
        printf("%d\n", res); break;
      }
      cnt++;
    }
  }
}

int main(void){
#ifndef ONLINE_JUDGE
  freopen("hoj12616.in", "r", stdin);
#endif
  int i, j;
  while (~scanf("%d%d", &n, &m) && (m||n)) {
    for (i = 0; i < m; ++i) {
      scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    }
    sort(edge, edge + m);
    kruscal();
  }

  return 0;
}

　　这货也不难。关键是，自己每次写kruscal的时候，总是忘了写init()函数……以后得注意了。　　可是比赛的时候，这货我都没学过……所以再简单也还是不会……所以，以后学东西得加快速度，至少知识点都知道，简单题得会做。

Read more