4 条题解

  • 7
    @ 2017-10-08 00:29:04

    题目中输入的就是最短路啦
    然后就看对于i到j这条路的最短路是否只有一条,是的话就输出这条路的长度,否则输出infty。
    why?
    因为假设删掉直接连接i与j的这条路(长度为最短路的长度),还有其他路径可以的话,i到j这条路的权值随你大到多少都行(显然吧)
    但删掉后就没有其他路径可以的话,就只有这条路可以(也显然吧)
    完毕。

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <queue>
    using namespace std;
    template <class _E> inline void read(_E &e)
    {
        e=0;bool ck=0;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')ck=1;ch=getchar();}
        while(ch<='9'&&ch>='0'){e=e*10+ch-'0';ch=getchar();}
        if(ck)e=-e;
    }
    int t,n;
    char inf[]={"infty"};
    int dis[101][101];
    int cnt[101][101];
    
    inline void floyd1()
    {
        for (int k=1;k<=n;++k)
            for (int i=1;i<=n;++i)
                for (int j=1;j<=n;++j)
                    if (i!=j && j!=k && i!=k)
                        if (dis[i][j]==dis[i][k]+dis[k][j])
                            ++cnt[i][j];
    }
    
    int main()
    {
        read(t);
        while (t--)
        {
            read(n);
            memset(cnt,0,sizeof cnt);
            for (int i=1;i<=n;++i)
                for (int j=1;j<=n;++j)
                    read(dis[i][j]);
            floyd1();
            for (int i=1;i<=n;++i)
            {
                for (int j=1;j<=n;++j)
                {
                    if (cnt[i][j])
                        printf("%s ",inf);
                    else printf("%d ",dis[i][j]);
                }
                puts("");
            }
        }
        return 0;
    }
    
  • 1
    @ 2017-10-07 23:40:12

    floyd跑最短路 //如果除了它本来的输入的路还有其他的最短路与它输入的路长度相等 那么就可以知道这两个点连不连通无所谓->infty
    //因为一开始输入的就是最短的路 所以不可能有比他小的情况
    //所以其他情况 输出 输入的路的长度即可
    //代码非常简单 为了图方便所以没有过多判断 无脑暴力

    #include<bits/stdc++.h>
    using namespace std;
    int t,n,mp[105][105],a[105][105];
    int main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n);
            for(int i=1;i<=n;++i)memset(mp[i],0x3f,sizeof 4*(n+1));
            for(int i=1;i<=n;++i){
                for(int j=1;j<=n;++j){
                    scanf("%d",&a[i][j]);
    //              mp[i][j]=a[i][j];
                }
            }
            for(int k=1;k<=n;++k){
                for(int i=1;i<=n;++i){
                    for(int j=1;j<=n;++j){
                        if(k==i or k==j)continue;
                        mp[i][j]=min(min(mp[i][k]+mp[k][j],min(a[i][k]+a[k][j],min(a[i][k]+mp[k][j],mp[i][k]+a[k][j]))),mp[i][j]);
                    }
                }
            }
            for(int i=1;i<=n;++i){
                for(int j=1;j<=n;++j){
                    if(i==j)printf("0%c",j!=n?' ':'\n');
                    else if(mp[i][j]==a[i][j])printf("infty%c",j!=n?' ':'\n');
                    else printf("%d%c",a[i][j],j!=n?' ':'\n');
                }
            }
        }
    }
     
    
  • -1
    @ 2017-10-08 16:53:02

    大家不应该忘记路径查找,你学弗洛伊德的时候一定听说过它的原理,其实就是DP。那么好了。我们只需要DP找一下路径,就像机器分配那道题。开始答案全部设成最大值。最后对a[i][i]设成0;最大值是INFTY.

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm> 
    using namespace std;
    const char s[10]={'i','n','f','t','y',' '};
    int t,n;
    int a[105][105],dis[105][105];
    void find(int i,int j){
        if (i==j) return;
        bool flag=false;
        for (int k=1;k<=n;k++){
            if (k==i||k==j) continue;
            if (a[i][j]==a[i][k]+a[k][j]){
                flag=true;
                find(i,k);
                find(k,j);
            }
        }
        if (flag==false){
            dis[i][j]=a[i][j];
        }
    }
    int main(){
        scanf("%d",&t);
        for (int q=1;q<=t;q++){
            memset(dis,127,sizeof(dis)); 
            scanf("%d",&n);
            for (int i=1;i<=n;i++){
                for (int j=1;j<=n;j++){
                    scanf("%d",&a[i][j]);
                }
            }
            for (int i=1;i<=n;i++){
                for (int j=1;j<=n;j++){
                    find(i,j);
                }
            }
            for (int i=1;i<=n;i++){
                dis[i][i]=0;
            }
            for (int i=1;i<=n;i++){
                for (int j=1;j<=n;j++){
                    if (dis[i][j]<99999999)
                        printf("%d ",dis[i][j]);
                    else cout<<s;
                }
                printf("\n");
            }
        }
    } 
    

    最后附上数据生成器。
    datemaker:

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<ctime>
    #include<cstdlib>
    #include<cstring>
    using namespace std;
    
    int n;
    int a[105][105];
    
    void print_a(){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j)
            printf("%d ",a[i][j]);
            printf("\n");
        }
    }
    int main(){
        freopen("t1.in","w",stdout);
        //t=12;
        printf("%d\n",12);
        srand(time(0));
        for(int pp=1;pp<=12;++pp){
        memset(a,0,sizeof(a));
        n=rand()%100+1;
        //n=7;
        printf("%d\n",n);
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j)
            a[i][j]=a[j][i]=rand()%256+1;
        }
        //print_a();
        for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        if(i!=k&&k!=j&&i!=j)
        a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
        print_a();  
        }
        return 0;
    }
    
    

    judge:

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    
    FILE *fin,*fout;
    const int N=105;
    int n[20],T;
    int a[20][N][N];
    int map[20][N][N];
    char s[10];
    
    
    int main(){
        fin=fopen("t1.in","r");
        int T;
        fscanf(fin,"%d",&T);
        for(int t=1;t<=T;++t){
            fscanf(fin,"%d",&n[t]);
        //  printf("%d\n",n[t]);
            for(int i=1;i<=n[t];++i)
            for(int j=1;j<=n[t];++j){
                fscanf(fin,"%d",&a[t][i][j]);
            }
        }
        fin=fopen("t1.out","r");
        for(int t=1;t<=T;++t){
        //  printf("%d\n",n[t]);
            for(int i=1;i<=n[t];++i)
            for(int j=1;j<=n[t];++j){
                fscanf(fin,"%s",s);
                if(s[0]=='i')map[t][i][j]=12345678;
                else sscanf(s,"%d",&map[t][i][j]);
            }
        }
        fout=fopen("t1.ans","w");
        fprintf(fout,"%d\n",T);
        for(int t=1;t<=T;++t){
            fprintf(fout,"%d\n",n[t]);
            for(int k=1;k<=n[t];++k)
            for(int i=1;i<=n[t];++i)
            for(int j=1;j<=n[t];++j)
            if(i!=j&&j!=k&&i!=k)
            map[t][i][j]=min(map[t][i][j],map[t][i][k]+map[t][k][j]);
            for(int i=1;i<=n[t];++i,fprintf(fout,"\n"))
            for(int j=1;j<=n[t];++j)
            fprintf(fout,"%d ",map[t][i][j]);
        }
        return 0;
    }
    
    

    对拍:

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    
    int main(){
        while(true){
            system("t1_datamaker.exe");
            system("t1.exe");
            system("t1_judge.exe");
            if(system("fc t1.in t1.ans"))break;
        }
        return 0;
    }
    
  • -4
    @ 2017-10-08 07:35:47

    题解
    这个题挺有意思。
    题目大意:给出的是所有两点间的最短路径,要求出图中两点的可能的最大边权,不会对最短路产生影响。
    怎么考虑这个问题呢?首先我们把给出的最短路暂定为两条边之间的边权,然后跑floyed,要求是不能只经过一条路到达(即把两点间的最短路抹掉),如果这样得出的两点间的最短路于原来的最短路相等,那么直接连接这两个点的边可以任意大,否则就不变。
    怎么能让他不能一条边到达呢?重新开一个数组记录。

    code:

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int T,n,d[101][101],m[101][101];
    
    int main()
    {
        scanf("%d",&T);
        while (T--)
        {
            scanf("%d",&n);
            for (int i=1; i<=n; i++)
                for (int j=1; j<=n; j++)
                    scanf("%d",&d[i][j]);
    //      for (int i=1; i<=n; i++) m[i][i]=0x7fffffff;
            memset(m,0x7f,sizeof(m));
            for (int k=1; k<=n; k++)
                for (int i=1; i<=n; i++)
                    for (int j=1; j<=n; j++)
                    if (i!=j&&j!=k&&i!=k)
                        m[i][j]=min(m[i][j],d[i][k]+d[k][j]);
            for (int i=1; i<=n; i++)
                for (int j=1; j<=n; j++)
                {
                    if (m[i][j]==d[i][j]&&i!=j) d[i][j]=-1;
                }
            for (int i=1; i<=n; i++)
            {
                for (int j=1; j<=n; j++)
                    if (d[i][j]==-1) printf("infty ");//==和=
                    else printf("%d ",d[i][j]);
                printf("\n");
            }
        }
        return 0;
    }
    
  • 1

信息

ID
2024
难度
4
分类
(无)
标签
(无)
递交数
365
已通过
146
通过率
40%
被复制
11
上传者