2012年12月15日 星期六

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':' ');
}

沒有留言:

張貼留言