藍橋杯 算法訓練 關聯矩陣（Java解題）

問題描述 　　有一個n個結點m條邊的有向圖，請輸出他的關聯矩陣。 輸入格式 　　第一行兩個整數n、m，表示圖中結點和邊的數目。n<=100,m<=1000。

　　接下來m行，每行兩個整數a、b，表示圖中有(a,b)邊。

　　注意圖中可能含有重邊，但不會有自環。 輸出格式 　　輸出該圖的關聯矩陣，注意請勿改變邊和結點的順序。 樣例輸入 5 9

1 2

3 1

1 5

2 5

2 3

2 3

3 2

4 3

5 4 樣例輸出 1 -1 1 0 0 0 0 0 0

-1 0 0 1 1 1 -1 0 0

0 1 0 0 -1 -1 1 -1 0

0 0 0 0 0 0 0 1 -1

0 0 -1 -1 0 0 0 0 1  說明：關聯矩陣法是因其整個程式如同一個矩陣排列而得名。關聯矩陣法是對多目标系統方案從多個因素出發綜合評定優劣程度的方法，是一種定量與定性相結合的評價方法，它用矩陣形式來表示各替代方案有關評價名額的評價值，然後計算各方案評價值的權重和，再通過分析比較，确定評價值權重和最大的方案即為最優方案。

對于一個無向圖G，pxq, p為頂點的個數，q為邊數。bij 表示在關聯矩陣中點i和邊j之間的關系。若點i和邊j之間是連着的，則bij = 1. 反之，則bij = 0. 

對于有向圖，若bij = 1，表示邊j離開點i。 若bij = -1， 表示邊j進入點i。 若bij = 0，表示邊j和點i不相關聯。 代碼：

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int m = s.nextInt();
		int[][] x = new int[n + 1][m + 1];
		for (int j = 1; j <= m; j++) {
			int a = s.nextInt();
			int b = s.nextInt();
			x[a][j] = 1;
			x[b][j] = -1;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				System.out.print(x[i][j] + " ");
			}
			System.out.println();
		}

	}
}