buglife SPOJ時間超過限制的Java

-3

任何暗示，避免受到時間限制超出了這個問題：_ http://www.spoj.com/problems/BUGLIFE/buglife SPOJ時間超過限制的Java

我怎麼能優化這些代碼

是有一個更快的方法讀取輸入

這些都是我的閱讀輸入法：_ http://ideone.com/GtSIAC

我的解決方案：_

import java.io.*; 
import java.util.*; 

public class buglife { 
    static int first; 
    static ArrayList[] graph = new ArrayList[2000]; 
    static int[] colour = new int[2000]; 
    static int[] queue = new int[2000]; 
    static int start; 
    static int index; 
    static int current; 

    public static boolean bfs(int f) { 
     for (int p = 0; p < first; p++) { 
     if (colour[p] != f && colour[p] != f + 1) { 
     int x; 
     start = 0; 
     index = 0; 
     queue[index++] = p; 
     colour[p] = f; 


      while (start < index) { 
        current = queue[start++]; 
        for (int i = 0; i < graph[current].size(); i++) { 
         x = (Integer) graph[current].get(i); 
         if (colour[x] != f && colour[x] != f + 1) { 
          if (colour[current] == f) { 
           colour[x] = f + 1; 
          } else if (colour[current] == f + 1) { 
           colour[x] = f; 
          } 

          queue[index++] = x; 
         } else if (colour[current] == colour[x]) { 

          return false; 
         } 

        } 
       } 

      } 
     } 
     return true; 
    } 

    public static void main(String[] args) throws IOException, Exception { 
     int second; 
     int one, two; 
     PrintWriter out = new PrintWriter(new BufferedWriter(
       new OutputStreamWriter(System.out))); 

     int test = nextInt(); 
     int j, k, i; 
     for (i = 1; i <= test; i++) { 
      first = nextInt(); 
      second = nextInt(); 
      for (k = 0; k < first; k++) 
       graph[k] = new ArrayList(); 

      for (j = 0; j < second; j++) { 

       one = nextInt(); 
       two = nextInt(); 
       graph[one - 1].add(two - 1); 
       graph[two - 1].add(one - 1); 
      } 

      out.println("Scenario #" + i + ":"); 
      if (bfs(2 * i) == false) { 
       out.println("Suspicious bugs found!"); 
      } else { 
       out.println("No suspicious bugs found!"); 
      } 

     } 
     out.flush(); 
    } 




}

來源

2013-07-23 ahmad diaa

TLE：異常的一些縮寫？如果有的話，它不被使用或太模糊。 – hexafraction

由於問題的時間限制爲5秒，所以超出了時間限制 –

然後編輯帖子。 – MathSquared

只使用BFS你解決不了，這個問題是關於二分圖

只要看看它在wikipedia

我解決了這個問題，比去年同期多。 my profile

來源

2013-08-04 01:46:17 Andres

buglife SPOJ時間超過限制的Java

回答

相關問題