[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();
}   

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注