SGU 164 Airlines

很神奇的題目。

題目敘述：

給一完全圖，每個邊有1~M其中一種顏色，選不超過(M+1)/2種顏色，使任意兩點只經過這些顏色時，最短路距離 <= 2
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

因為邊分成是你選的，跟你不選的兩種，所以可以把題目化簡成：

有一完全圖，邊只有兩種顏色，選一種顏色，使任兩點最短路距離<=2

可以證明，這兩種顏色，至少有一種會符合任兩點最短路距離<=2
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

我爸的證明：XD

設顏色為A, B，任一點都有A的度數 degA(u) 和B的度數 degB(u)

選一個點，使他的某顏色度數是所有點的某顏色度數當中，最大的

設該點為 u，且他連比較多條邊的顏色是A，於是你選擇 A 這個顏色

你可以把他看成兩群，一群是 u 連 A 過去的，一群是 u 連 B 過去的

連A的那群互相都可以相連（透過 u），所以先不理他

至於連B的那群，假設某點連到A的那群不存在一條A邊，也就是全部B邊

那麼加上他連到 u 的B邊，最少就有degA(u)+1條，也>degA(u)了，矛盾

所以所有B那群的點連到A的那群至少會有一條A邊

而透過-> A那群 -> u -> B那群 or -> A那群 -> u ->  A那群

所有的點都可以連到所有的點（距離 <= 2），QED
 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

所以你可以隨便找一半的顏色作為一群，另一半顏色做另一群

判斷某一群是否皆<=2，若沒有，那就是另一群（用Floyd-Warshall）

//By momo
#include<cstdio>
#include<algorithm>
#define N 210
#define INF 999999999
using namespace std;
int n, m, G[N][N], st, en, fl;
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &G[i][j]);
            if(i == j) continue;
            G[i][j] = (G[i][j] <= (m+1)/2)?1:INF;
        }
    }
   
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
   
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(G[i][j] > 3) fl = 1;

    if(fl) st = (m+1)/2+1, en = m;
    else st = 1, en = (m+1)/2;
    printf("%d\n", en-st+1);
    for(int i = st; i <= en; i++) printf("%d%c", i, i == en?'\n':' ');
}