[SGU 164 Airlines]floyd、巧妙证明

【题目大意】给出一个无向完全图，图中的边都被染成了某种颜色[1，M]，求一个颜色集合，使得包含了这些边以后，图中的任意两点的最短路<=3

【算法分析】

可以证明将前(M+1)/2颜色分成一组，其余的颜色分成一组以后，必有一组符合条件。

下面别人的证明：

如果A集合符合题目要求，则命题成立，否则假设A集合不符合题目要求，也就是存在两个点a,b，他们的距离大于3、或者两者无法互相到达。

下面考虑B集合。

对于任意点对(x,y)，如果 A，必有∈B，所以在B中的距离<=3。

对于任意点对(x,y)，∈A，如果a在A中不和x,y中的任意一个有直接连边，则在B中存在；如果b在A中不和x,y中的任意一个有直接连边，则在B中存在。因此可以假设a, b在A中都和x或y有直接联系。

这样在A中就存在或类似的路径，长度不超过3。这和我们的假设前提“a,b在A中的距离超过3或者不连通”矛盾。 因此不可能存在a,b在A中都和x, y有直接联系这种情况。

所以不论∈A还是 A，他们在B中的距离都不超过3。所以，如果A不满足题目要求，B必然满足要求。

命题得证明。

【其它】1A

998230 10.02.10 16:43 edward 164 .CPP Accepted 95 ms 271 kb

【CODE】

#include #include

int a[200][200],n,m,g[200][200];

void init(){
    scanf("%d%d",&n,&m);
    for (int i=0;i      for (int j=0;j        scanf("%d",&a[i][j]);
}   

bool flag(int ed){
    memset(g,50,sizeof(g));
    for (int i=0;i      for (int j=0;j        if (a[i][j]<=ed) g[i][j]=1;
    for (int k=0;k      for (int i=0;i        for (int j=0;j          if (g[i][k]+g[k][j]            g[i][j]=g[i][k]+g[k][j];
    for (int i=0;i      for (int j=0;j        if (g[i][j]>3) return false;
    return true;
}   

void work(){
    if (flag((m+1)/2)){
        printf("%dn",(m+1)/2);
        for (int i=1;i<=(m+1)/2;i++){
          if (i!=1) printf(" ");
          printf("%d",i);
        }   
        printf("n");
    }   
    else{
        printf("%dn",m-(m+1)/2);
        for (int i=(m+1)/2+1;i<=m;i++){
            if (i!=(m+1)/2) printf(" ");
            printf("%d",i);
        }   
        printf("n");
    }   
}   

int main(){
    init();
    work();
}