2014
08-20

# 二分图判断-Problem A.Bad Horse(codejam)

public class BasHorse {
static int n;
static int T, index, cnt;
static int map[][];

public static void main(String[] args) {
try {
String path = "D:\\CPP\\code-jam\\A-small-practice-2.in";
Scanner scan = new Scanner(new File(path));
String outputPath = path.replace(".in", "out.txt");
File file = new File(outputPath);
FileOutputStream fos = new FileOutputStream(file);
T = scan.nextInt();
Map<String,Integer> mapSet = new HashMap<String,Integer>();
for(int i=0; i<T; i++){
mapSet.clear();
n = scan.nextInt();
index = 0;
map = new int[n*2][n*2];//最多会有2n个
for(int j =0; j<n; j++){
String str1 = scan.next();
Integer a ;
if( (a = mapSet.get(str1)) == null){
a = index;
mapSet.put(str1, index);
index++;
}
String str2 = scan.next();
Integer b ;
if( (b = mapSet.get(str2)) == null){
b = index;
mapSet.put(str2, index);
index++;
}
map[a][b] = 1;
map[b][a] = 1;

}
boolean isbit = isBipartite(map,index);
String output = "Case #" + (i+1) + ": ";
if(isbit) output += "Yes\r\n";
else output += "No\r\n";
try {
fos.write(output.getBytes());
} catch (IOException e) {
e.printStackTrace();
}
System.out.println(isbit);
}

} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}

private static boolean isBipartite(int[][] map,int n) {
//colorArr[i] 代表第i个结点的颜色
int colorArr[] = new int[n];
colorArr[0] = 1;
Queue<Integer> queue = new LinkedList<Integer>();
while(!queue.isEmpty()){
int top = queue.poll();
for(int i=0; i<n; i++){
if(map[top][i] == 1 && colorArr[i] == 0){
colorArr[i] = 3 - colorArr[top];//两种颜色 1和2 交替着色
}else if(map[top][i] == 1 &&  colorArr[i] == colorArr[top] ){
return false;
}
}
}
return true;
}
}

1. 样例输出和程序输出不吻合，修改一下样例输出吧。我用的是VC编译器，会提示我的i和j变量重复定义

2. [email protected]

3. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的

4. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了