hdu4081 最小樹+DFS或者次小樹的變形

題意:

      給你一個全圖,在裡面找到一棵樹,這棵樹最多隻有一條邊可以不是最小樹(也可以是), 要求 那對特殊的邊的兩個權值/除了這條邊其他邊的和最大.

思路:

     方法有很多,最少有三種方法,我用兩種方法做的,别的暫時沒想到(太弱了);

     第一種:

            先求出來一顆最小樹,然後枚舉樹上的邊,枚舉到每一條邊的時候就假設把這條邊删除了,然後分成兩個集合,我們隻要在這兩個集合之間連一條邊,肯定就是樹了,那麼怎麼連呢,我們可以直接搜尋兩個集合中分别權值最大的那個點,假設連接配接這兩條邊,因為要就該邊的權值/非該邊的所有和最大,每次枚舉相當于分母固定了(最小樹 - 目前枚舉的邊),隻要找到最大的分子就行了,是以在兩個集合裡面找最大的點.就這樣周遊到最後,取得最大值就行了.

    第二種:

          第二種是和上面的想法相反的,是分子固定找分母,做法也是先找到一顆最小樹,然後枚舉所有邊,當枚舉該邊的時候就假設該邊就是那個特殊的邊,那麼權值分子就固定是邊的兩個點的權值,那麼分子呢,分兩種情況,如果目前枚舉的邊不是最小樹上的邊,那麼加上這條邊後就一定會形成環,我們既然要比值最大,而且還必須是棵樹,那就必須在環上删除一條最大的邊(不算目前這條邊),如果目前的邊是最小樹上的邊,那麼就删除該邊就行了,其實兩種情況的寫法都一樣,分母都是 最小樹 - max(u ,v),max(u ,v)是樹上u,v,之間最長的邊,

可以在枚舉前搜尋一遍求出來樹上任意兩點之間的最長邊(時間是o(n^2));就這樣周遊到最後取最小就行了.....

我的兩個解法都跑了900多,原因是最小樹用的K求的,其實應該用P求會快很多,因為P是針對稠密圖的,後來的4756 用K就過不去,必須用P + 樹形dp 優化.

最小樹 + DFS

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>



using namespace std;



typedef struct

{

   int x ,y ,w;

}NODE;



typedef struct

{

   int to ,next;

}STAR;



typedef struct

{

   int a ,b;

   double x;

}EDGE;



NODE node[1100];

EDGE edge[1100 * 1100 /2];

STAR E[1100*2];

int list[1100] ,tot;

int mer[1100] ,MAX;

int mk[1100*2];

bool mark_dfs[1100];



int finds(int x)

{

   if(x == mer[x])

   return x;

   mer[x] = finds(mer[x]);

}



void add(int a ,int b)

{

   E[++tot].to = b;

   E[tot].next = list[a];

   list[a] = tot;

}



bool camp(EDGE a ,EDGE b)

{

   return a.x < b.x;

}







void DFS(int s ,int w)

{

   if(MAX < w)

   MAX = w;

   for(int k = list[s] ;k ;k = E[k].next)

   {

      int to = E[k].to;

      if(mark_dfs[to]) continue;

      mark_dfs[to] = 1;

      DFS(to ,node[to].w);

   }

}



int main ()

{

   int t ,n ,i ,j;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d" ,&n);

      for(i = 1 ;i <= n ;i ++)

      scanf("%d %d %d" ,&node[i].x ,&node[i].y ,&node[i].w);

      int tmp = 0;

      for(i = 1 ;i <= n ;i ++)

      for(j = i + 1 ;j <= n ;j ++)

      {

         int xx = node[i].x - node[j].x;

         int yy = node[i].y - node[j].y;

         double dis = sqrt(xx * xx * 1.0 + yy * yy * 1.0);

         edge[++tmp].a = i;

         edge[tmp].b = j;

         edge[tmp].x = dis;

      }

      

      memset(list ,0 ,sizeof(list));

      tot = 1;

      double sum = 0;

      sort(edge + 1 ,edge + tmp + 1 ,camp);

      int mkt = 0;

      for(i = 1 ;i <= n ;i ++)mer[i] = i;

      

      for(i = 1 ;i <= tmp ;i ++)

      {

         int x = finds(edge[i].a);

         int y = finds(edge[i].b);

         if(x == y) continue;

         mer[x] = y;

         sum += edge[i].x;

         add(edge[i].a ,edge[i].b);

         add(edge[i].b ,edge[i].a);

         mk[++mkt] = i; 

      } 

      double ans = 0;

      for(i = 1 ;i <= mkt ;i ++)

      {

         int ii = mk[i];

         int a = edge[ii].a;

         int b = edge[ii].b;

         MAX = node[a].w;

         memset(mark_dfs ,0 ,sizeof(mark_dfs));

         mark_dfs[a] = mark_dfs[b] = 1;

         DFS(a ,node[a].w);

         int m1 = MAX;

         memset(mark_dfs ,0 ,sizeof(mark_dfs));

         mark_dfs[a] = mark_dfs[b] =1;

         MAX = node[b].w;

         DFS(b ,node[b].w);

         int m2 = MAX;

         

         double aa = (m1 + m2) * 1.0 / (sum - edge[ii].x);

         if(ans < aa)

         ans = aa;

      }

      printf("%.2lf\n" ,ans);

   }

   return 0;

}





有點像次小生成樹



#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>



#define N (1000 + 100)



using namespace std;



typedef struct

{

   int x ,y ,w;

}NODE;



typedef struct

{

   int a ,b;

   double x;

}EDGE;



typedef struct

{

   int to ,next;

   double dis;

}STAR;



NODE node[N];

EDGE edge[N*N/2];

STAR E[N*2];



int list[N] ,tot;

int mark_dfs[N];

double maxe[N][N];

int mer[N];



void add(int a, int b ,double c)

{

   E[++tot].to = b;

   E[tot].dis = c;

   E[tot].next = list[a];

   list[a] = tot;

}



int finds(int x)

{

   if(x == mer[x]) return x;

   return mer[x] = finds(mer[x]);

}



bool camp(EDGE a ,EDGE b)

{

   return a.x < b.x;

}



double maxx(double x ,double y)

{

   return x > y ? x : y;

}



void dfs_max(int s ,double nowmax ,int oo)

{

   for(int k = list[s] ;k ;k = E[k].next)

   {

      int to = E[k].to;

      if(mark_dfs[to]) continue;

      mark_dfs[to] = 1;

      maxe[oo][to] = maxx(nowmax,E[k].dis);

      dfs_max(to ,maxx(nowmax,E[k].dis),oo);

   }

   return;

}



int main ()

{

   int t ,n ,i ,j;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d" ,&n);

      for(i = 1 ;i <= n ;i ++)

      scanf("%d %d %d" ,&node[i].x ,&node[i].y ,&node[i].w);

      int tmp = 0;

      for(i = 1 ;i <= n ;i ++)

      for(j = i + 1 ;j <= n ;j ++)

      {

         int xx = node[i].x - node[j].x;

         int yy = node[i].y - node[j].y;

         double dis = sqrt(xx * xx * 1.0 + yy * yy * 1.0);

         edge[++tmp].a = i;

         edge[tmp].b = j;

         edge[tmp].x = dis;

      }

      

      sort(edge + 1 ,edge + tmp + 1 ,camp);

      memset(list ,0 ,sizeof(list));

      tot = 1;

      double T_sum = 0;

      for(i = 1 ;i <= n ;i ++) mer[i] = i;

      for(i = 1 ;i <= tmp ;i ++)

      {

         int a = edge[i].a;

         int b = edge[i].b;

         int x = finds(a);

         int y = finds(b);

         if(x == y) continue;

         mer[x] = y;

         T_sum += edge[i].x;

         add(a ,b ,edge[i].x);

         add(b ,a ,edge[i].x);

      }

      

      for(i = 1 ;i <= n ;i ++)

      {

         memset(mark_dfs ,0 ,sizeof(mark_dfs));

         mark_dfs[i] = 1;

         dfs_max(i ,0 ,i);

      }

      

      double ans = 0;      

      

      for(i = 1 ;i <= tmp ;i ++)

      {

         int a = edge[i].a;

         int b = edge[i].b;

         double now;

         now = 1.0 * (node[a].w + node[b].w) / (T_sum - maxe[a][b]);

         if(ans < now) ans = now;

      }

      

      printf("%.2lf\n" ,ans);

   }

   return 0;

}