Google，资源限制下的最大唯一访问量，图中的负值

Question

我很难弄清楚这是哪种问题。我还是个学生，还没有上过图论/线性优化课。

我唯一确定的是检查负循环，因为这意味着您可以将资源限制提高到无穷大，允许您捡起每只兔子。我不知道选择下一条路的“理由”。我也不知道什么时候终止，因为您可以继续使用所有的边，使资源限制永远降到0以下，但是永远不要转义。

我并不是真的在寻找代码(因为这是一个编码挑战)，只是问题的类型(Ex:最大流量，最长路径，最短路径，等等)。如果你的算法已经符合这一点，那就太棒了。谢谢。

从你的起点移动到所有兔子和舱壁所需的时间将以整数方阵的形式提供给你。每一排都会告诉你开始的时间，第一只兔子，第二只兔子，.，最后一只兔子，以及按顺序排列的舱壁。行的顺序遵循相同的模式(开始，每个兔子，舱壁)。兔子可以跳到你的怀里，所以捡起来是瞬间的，到达舱壁的同时，它的封口仍然允许一个成功的，如果戏剧性，逃跑。(别担心，任何你不接的兔子都能和你一起逃走，因为它们不再需要携带你捡到的兔子了。)如果你愿意的话，你可以重新参观不同的地方，搬到舱壁上并不意味着你必须马上离开--如果时间允许，你可以从舱壁上搬来搬去接更多的兔子。 除了花时间在兔子之间旅行外，一些路径还会与空间站的安全检查点交互，并给时钟增加时间。在时钟上增加时间会延迟舱门的关闭，如果时间恢复到0，或者在门已经关闭后有一个正数，就会触发舱壁重新打开。因此，可以在一个圆圈中行走并保持时间:也就是说，每次遍历一条路径时，都会使用或增加相同的时间。 写一个函数的形式回答(时间，time_limit)，以计算你能捡到的兔子最多，它们是哪些兔子，同时仍然逃避通过舱壁之前，大门永远关闭。如果有多组大小相同的兔子，则按排序顺序返回具有最低囚犯in (作为索引)的兔子集。兔子被表示为一个按囚犯ID排序的列表，第一个兔子是0。最多有5只兔子，而time_limit是一个最多为999的非负整数。

Answer 1

它基本上是一个规划问题。一般的规划方法是确定世界的可能状态、初始状态、状态之间的转换和最终状态。然后搜索这个数据所暗示的图表，最简单的是使用宽度优先搜索。

对于这个问题，相关的状态是：(1)剩下多少时间，(2)我们抓到的兔子，(3)我们现在所处的位置。这意味着1000个时钟设置(我将马上讨论增加的时间)乘以2^5 = 32个兔子子集乘以7个位置=224,000个可能的状态，这对于一个人来说是很多的，而不是一台计算机。

我们可以通过从约翰逊算法上偷一个技巧来处理额外的时间。正如Tymur在一条评论中所建议的，运行Bellman--Ford，或者找到一个负循环(在这种情况下，所有的兔子都可以通过在负循环中运行足够多的时间来保存)，或者当应用时，使所有的时间都非负。不要忘记根据起始位置和舱壁之间的电位差来调整启动时间。

Answer 2

这就对了。我昨天开始使用Google Foobar了。我马上就要开始5级了。这是我在第4级的第二个问题，这个解决方案足够快，因为我试着不使用utils类来回忆录状态。不管怎么说，我喜欢这段经历。这是我迄今为止解决的最好的问题，因为我使用了弗洛伊德-沃尔(如果有负循环的话)、Bellman(作为像Johnson's和Suurballe‘s等算法中常用的重量调整步骤的实用函数)、Johnson(重量调整！)、DFS(用于跨步骤递归)，甚至使用自行设计的散列函数进行回忆录:)快乐编码！

public class Solution
{

public static final int INF = 100000000;
public static final int MEMO_SIZE = 10000;
public static int[] lookup;
public static int[] lookup_for_bunnies;

public static int getHashValue(int[] state, int loc)
{
    int hashval = 0;
    for(int i = 0; i < state.length; i++)
        hashval += state[i] * (1 << i);
    hashval += (1 << loc) * 100;

    return hashval % MEMO_SIZE;
}

public static boolean findNegativeCycle(int[][] times)
{
    int i, j, k;
    int checkSum = 0;
    int V = times.length;
    
    int[][] graph = new int[V][V];
    for(i = 0; i < V; i++)
        for(j = 0; j < V; j++)
        {
            graph[i][j] = times[i][j];
            checkSum += times[i][j];
        }
    if(checkSum == 0)
        return true;
        
    for(k = 0; k < V; k++)
        for(i = 0; i < V; i++)
            for(j = 0; j < V; j++)
                if(graph[i][j] > graph[i][k] + graph[k][j])
                    graph[i][j] = graph[i][k] + graph[k][j];
                
    for(i = 0; i < V; i++)
        if(graph[i][i] < 0)
            return true;
    return false;
}
    
public static void dfs(int[][] times, int[] state, int loc, int tm, int[] res)
{
    int V = times.length;
    if(loc == V - 1)
    {
        int rescued = countArr(state);
        int maxRescued = countArr(res);
        
        if(maxRescued < rescued)
            for(int i = 0; i < V; i++)
                res[i] = state[i];
        
        if(rescued == V - 2)
          return;
    }
    else if(loc > 0)
      state[loc] = 1;
    
    int hashval = getHashValue(state, loc);
    if(tm < lookup[hashval])
        return;
    else if(tm == lookup[hashval] && countArr(state) <= lookup_for_bunnies[loc])
        return;
    else
    {
        lookup_for_bunnies[loc] = countArr(state);
        lookup[hashval] = tm;
        for(int i = 0; i < V; i++)
        {
            if(i != loc && (tm - times[loc][i]) >= 0)
            {
                boolean stateCache = state[i] == 1;
                dfs(times, state, i, tm - times[loc][i], res);
                if(stateCache)
                    state[i] = 1;
                else
                    state[i] = 0;
            }
        }
    }
}

public static int countArr(int[] arr)
{
    int counter = 0;
    for(int i = 0; i < arr.length; i++)
      if(arr[i] == 1)
        counter++;
    return counter;
}

public static int bellmanFord(int[][] adj, int times_limit)
{
    int V = adj.length;
    int i, j, k;
    int[][] graph = new int[V + 1][V + 1];
    
    for(i = 1; i <= V; i++)
      graph[i][0] = INF;
      
    for(i = 0; i < V; i++)
      for(j = 0; j < V; j++)
        graph[i + 1][j + 1] = adj[i][j];
    
    int[] distance = new int[V + 1] ;
    for(i = 1; i <= V; i++)
      distance[i] = INF;
      
    for(i = 1; i <= V; i++)
      for(j = 0; j <= V; j++)
      {
        int minDist = INF;
        for(k = 0; k <= V; k++)
          if(graph[k][j] != INF)
            minDist = Math.min(minDist, distance[k] + graph[k][j]);
        distance[j] = Math.min(distance[j], minDist);
      }

    for(i = 0; i < V; i++)
      for(j = 0; j < V; j++)
        adj[i][j] += distance[i + 1] - distance[j + 1];

    return times_limit + distance[1] - distance[V];
}

public static int[] solution(int[][] times, int times_limit)
{
    int V = times.length;
    if(V == 2)
        return new int[]{};
    if(findNegativeCycle(times))
    {
        int ans[] = new int[times.length - 2];
        for(int i = 0; i < ans.length; i++)
          ans[i] = i;
        return ans;
    }
    lookup = new int[MEMO_SIZE];
    lookup_for_bunnies = new int[V];
    for(int i = 0; i < V; i++)
        lookup_for_bunnies[i] = -1;
    
    times_limit = bellmanFord(times, times_limit);
    int initial[] = new int[V];
    int res[] = new int[V];
    
    dfs(times, initial, 0, times_limit, res);
    
    int len = countArr(res);
    int ans[] = new int[len];
    int counter = 0;
    for(int i = 0; i < res.length; i++)
      if(res[i] == 1)
      {
        ans[counter++] = i - 1;
        if(counter == len)
          break;
      }
    
    return ans;
}

}