找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 875|回复: 0
收起左侧

[资源分享] 38 Connected Graph

[复制链接]

62

主题

1

精华

202

积分

高级会员

Rank: 3Rank: 3

积分
202
发表于 6-9-2015 11:27 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
这是道动态规划题,我自己做着挺有难度的。一开始我想递推方法想错了,想从连接前n个推导出如何连接前n+1个。这样想是不对的,n个相连的最后一步,可以是把大小为1和大小为n-1的连通图相连,也可以是把大小为2和大小为n-2的连通图相连。
意识到自己的错误后,我开始考虑其它的递推方法。可以从第k天的连通情况推导出第k+1天的连通情况,发现这样可行,能包含
所有情况,就是状态表示复杂了点。第k天可以有好多种可能状态,每种状态我用现有的连通图大小和个数表示,如大小为1的连通
图2个,大小为2的连通图1个,然后每个状态有一个可能的概率。从第k天的一种状态,推到第k+1天的一种状态,要么保持现有连通
图大小和个数,只增加连通图内部的道路数,要么选两个连通图连成一个。状态和递推方法都确定好后,再来确定结束条件,如果某天
的某种状态是n个点都连起来了,即有一个大小为n的连通图,这个状态就不用再往下推了,把它按概率加到预期天数了即可。
这道题我的解法比较复杂,时间效率也不高。因为时间复杂度不好算,我直接算了所有可能的状态数,大概在5000左右,所以虽然步骤复杂,
但还是可以勉强在秒级通过的。有更好的方法希望不吝指教~
顺便说下,这道题的答案竟然是求预期天数的下限,确实出人意料,最好能在题目中说明。
代码如下:
  1. class Node {
  2.     // s【i】 means the count of connected parts in size i.
  3.     int[] s = new int[31];
  4.   }

  5.   class NodeComparator implements Comparator<Node> {
  6.     public int compare(Node n1, Node n2) {
  7.       for (int i = 0; i < n1.s.length; ++i) {
  8.         if (n1.s【i】 != n2.s【i】) {
  9.           return n1.s【i】 - n2.s【i】;
  10.         }
  11.       }
  12.       return 0;
  13.     }
  14.   }

  15.   public int connectThem(int n) {
  16.     if (n <= 1) {
  17.       return 0;
  18.     }
  19.     // dp【i】 represents all the situations in day i.
  20.     // Each node in the tree represents a possible situation in day i.
  21.     ArrayList<TreeMap<Node, Double>> dp = new ArrayList<TreeMap<Node, Double>>();
  22.     Node node = new Node();
  23.     node.s[1] = n;
  24.     NodeComparator comparator = new NodeComparator();
  25.     TreeMap<Node, Double> map = new TreeMap<Node, Double>(comparator);
  26.     map.put(node, 1.0);
  27.     dp.add(map);

  28.     Node searchNode = new Node();
  29.     searchNode.s[n] = 1;

  30.     double expectedDays = 0.0;

  31.     for (int i = 0; i < dp.size(); ++i) {
  32.       map = dp.get(i);
  33.       TreeMap<Node, Double> nextMap = new TreeMap<Node, Double>(comparator);
  34.       int existRoad = i;
  35.       for (Node n1 : map.keySet()) {
  36.         double curPro = map.get(n1);
  37.         // the max roads can contains if keeping current connected parts unchanged.
  38.         int curMaxRoad = getCurMaxRoad(n1);

  39.         int oldConnectRoad = curMaxRoad - existRoad;

  40.         // possible roads that can connect two parts.
  41.         int newConnectRoad = n * (n - 1) / 2 - curMaxRoad;
  42.         
  43.         int possibleRoad = oldConnectRoad + newConnectRoad;

  44.         if (oldConnectRoad != 0) {
  45.           addPossible(nextMap, n1, curPro * oldConnectRoad / possibleRoad);
  46.         }
  47.         int addRoad = 0;
  48.         for (int j = 1; j < 30; ++j) {
  49.           if (n1.s[j] == 0) {
  50.             continue;
  51.           }
  52.           int count1 = n1.s[j];
  53.           n1.s[j]--;
  54.           if (n1.s[j] >= 1) {
  55.             int connectRoad = count1 * (count1 - 1) / 2 * j * j;
  56.             n1.s[j]--;
  57.             n1.s[j+j]++;
  58.             addPossible(nextMap, n1, curPro * connectRoad / possibleRoad);
  59.             n1.s[j]++;
  60.             n1.s[j+j]--;
  61.             addRoad += connectRoad;
  62.           }
  63.           for (int k = j + 1; k < 30; ++k) {
  64.             if (n1.s[k] == 0) {
  65.               continue;
  66.             }
  67.             int connectRoad = count1 * n1.s[k] * j * k;
  68.             n1.s[k]--;
  69.             n1.s[j+k]++;
  70.             addPossible(nextMap, n1, curPro * connectRoad / possibleRoad);
  71.             n1.s[k]++;
  72.             n1.s[j+k]--;
  73.             addRoad += connectRoad;
  74.           }
  75.           n1.s[j]++;
  76.         }
  77.         if (addRoad != newConnectRoad) {
  78.           return -1;
  79.         }
  80.       }

  81.       Double value = nextMap.get(searchNode);
  82.       if (value != null) {
  83.         expectedDays += value * (i + 1);
  84.         nextMap.remove(searchNode);
  85.       }
  86.       if (nextMap.size() > 0) {
  87.         dp.add(nextMap);
  88.       }
  89.     }
  90.     return (int)Math.floor(expectedDays);
  91.   }

  92.   void addPossible(TreeMap<Node, Double> map, Node n, double pro) {
  93.     Node newNode = new Node();
  94.     for (int i = 1; i < n.s.length; ++i) {
  95.       newNode.s【i】 = n.s【i】;
  96.     }
  97.     Double oldValue = map.get(newNode);
  98.     if (oldValue != null) {
  99.       pro += oldValue;
  100.     }
  101.     map.put(newNode, pro);
  102.   }

  103.   int getCurMaxRoad(Node n) {
  104.     int road = 0;
  105.     for (int i = 1; i < n.s.length; ++i) {
  106.       road += n.s【i】 * i * (i - 1) / 2;
  107.     }
  108.     return road;
  109.   }
复制代码


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表