85 条题解

  • 4
    @ 2017-05-07 13:00:18
    /*
    呼呼~只能说语文没学好这道题真心做的累呀23333
    一开始看到这道题想都没想就想到了toposort+关键路径(无视语病问题)
    然后突然发现好像不是这个意思
    仔细一看    突然感觉好像不需要AOV?
    或者说不能AOV?
    倒是有点像求最长路~
    手算一下样例自己找下规律
    发现最长路的确是可以的 考虑到n,m都很小
    直接可以Floyd求最长路~
    对于输入的点和边构成的G(V,E)Floyd更新最长路(注意结点数应该是n+1)
    然后一定要注意,我们选择的最长路的起点和终点是固定的,只能是1和n+1
    所以就直接输出a[1][n+1]就好啦
    对于路径上的点的判断就简单啦~
    一个循环找一下所有点,如果有a[1][i]+a[i][n+1]==a[1][n+1]
    那么就是路径上的点,输出即可
    这道题就做出来了    所以一定要细心不要被一大串的题目弄昏了
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    int n;
    int m;
    int a[130][130];
    
    void init()
    {
        int x,y,w;
        scanf("%d",&n);     n++;
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            a[x][y]=w;
        }
    }
    
    void Floyd()
    {
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(i!=j)
                        if(a[i][k]>0&&a[k][j]>0)
                            a[i][j]=max(a[i][j],a[i][k]+a[k][j]);
    }
    
    void output()
    {
        printf("%d\n",a[1][n]);
        for(int i=1;i<=n;i++)
            if(a[1][i]+a[i][n]==a[1][n])
                printf("%d ",i);
    }
    
    int main()
    {
        init();
        Floyd();
        output();
    }
         
    
  • 1
    @ 2021-08-23 08:47:03
    #include<bits/stdc++.h>
    using namespace std;
    
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while (!isdigit(ch)){
            if (ch == '-')
                f = -1;
                ch = getchar();
        }
        while (isdigit(ch)){
            x = x * 10 + ch -48;
            ch = getchar();
        }
        return x * f;
    }
    
    inline void write(int x){
        if (x < 0){
            putchar('-');
            write(-x);
            return;
        }
        if (x >= 10)
            write(x / 10);
        putchar(x % 10 + 48);
        return;
    }
    
    inline void writeln(int x){
        write(x);
        puts("");
        return;
    }
    
    inline void writesp(int x){
        write(x);
        putchar(' ');
        return;
    }
    
    int f[199][199];
    signed main(){
        int n = read(), m = read();
        n++;
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= m; ++ i)
        f[read()][read()] = read();
        for (int k = 1; k <= n; ++ k)
            for (int i = 1; i <= n; ++ i)
                if (i != k)
                    for (int j = 1; j <= n; ++ j)
                        if (i != j && k != j && f[i][k] && f[k][j])
                            f[i][j] = max(f[i][j], f[i][k] + f[k][j]);
        writeln(f[1][n]);
        for (int i = 1; i <= n; ++ i)
            if (f[1][i] + f[i][n] == f[1][n])
                writesp(i);
        return 0;
    }
    
  • 1
    @ 2020-05-21 21:38:31

    明显的动态规划

    #include<iostream>
    #include<string.h>
    #include<fstream>
    using namespace std;
    int n,m,g[105][105]={0};
    int main(){
        cin>>n>>m;
         n++;
        for(int i=1;i<=m;++i){
          int a,b,c;
          cin>>a>>b>>c;
          g[a][b]=c;
                }
        for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
        if(i!=k)
        for(int j=1;j<=n;++j)
        if(i!=j&&j!=k&&g[i][k]!=0&&g[k][j]!=0)
        if(g[i][j]<g[i][k]+g[k][j])
        g[i][j]=g[i][k]+g[k][j];
         cout<<g[1][n]<<endl;
        cout<<1;
        for(int i=2;i<=n;++i)
        if(g[1][i]+g[i][n]==g[1][n])
        cout<<" "<<i;
        cout<<endl; 
        return 0;
     } 
    
  • 1
    @ 2018-04-28 08:24:04

    /*
    蒟蒻的思路:
    1.先跑一遍Floyd求出完成整个游戏需要至少多长时间;
    2.因为游戏总是要开始的,所以肯定是有 “1 ”,所以再输出 “1 ”;
    3.因为在跑Floyd的时候已经求出了每个环节完成的最小值,所以只要判断是否符合ed[1][i]加上ed[i][n+1]即可;
    以下代码......
    */

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,m,ed[100][100];
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1,a,b,c;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            ed[a][b]=c;
        }
        for(int k=1;k<=n+1;k++)
            for(int i=1;i<=n+1;i++)
                for(int j=1;j<=n+1;j++){
                    if(i!=j&&j!=k&&ed[i][k]&&ed[k][j])
                    if(ed[i][j]<ed[i][k]+ed[k][j])
                    ed[i][j]=ed[i][k]+ed[k][j];
                }
        printf("%d\n",ed[1][n+1]);
        printf("1 "); 
        for(int i=2;i<=n+1;i++)
            if(ed[1][i]+ed[i][n+1]==ed[1][n+1])
                printf("%d ",i);
        return 0;       
    }
    
  • 0
    @ 2017-08-14 11:00:50
    
    var n,m,i,x,y,z,j,k:longint;
    a:array[0..300,0..300] of longint;
    begin
    readln(n);
    readln(m);
    fillchar(a,sizeof(a),0);
    for i:=1 to m do
    begin
    read(x,y,z);
    a[x,y]:=z;
    end;
    for k:=1 to n+1 do
    for i:=1 to n+1 do if (i<>k) then
    for j:=1 to n+1 do
    if (a[i,k]+a[k,j]>a[i,j])and(i<>j)and(j<>K)and(a[i,k]<>0)and(a[k,j]<>0) then a[i,j]:=a[i,k]+a[k,j];
    writeln(a[1,n+1]);
    write(1,' ');
    for i:=2 to n do
    if a[1,i]+a[i,n+1]=a[1,n+1] then write(i,' ');
    write(n+1);
    end.
    
    
  • 0
    @ 2017-05-10 23:32:40

    Accepted

    状态 耗时 内存占用

    #1 Accepted 0ms 1016.0KiB
    #2 Accepted 0ms 1012.0KiB
    #3 Accepted 0ms 1012.0KiB
    #4 Accepted 0ms 1020.0KiB
    #5 Accepted 0ms 1016.0KiB
    #6 Accepted 0ms 1008.0KiB
    #7 Accepted 0ms 1016.0KiB
    #8 Accepted 0ms 1012.0KiB
    #9 Accepted 0ms 1016.0KiB
    #10 Accepted 0ms 1020.0KiB

    这题有点奇怪啊。题意有点模糊,估计是语文不及格的原因。
    两条路长度一样的时候被坑了一波,要把两条路上的点都输出。

    #include<stdio.h>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int MAXN = 101;
    int map[MAXN][MAXN];
    int dis[MAXN];
    int vis[MAXN];
    int ans[MAXN];
    int n;
    
    void SPFA() {
        int u = 1;
        dis[u] = 0;
        queue<int> Q;
        Q.push(u);
        vis[u] = 1;
        int i; int temp;
        while (!Q.empty()) {
            u = Q.front();
            Q.pop();
            vis[u] = 0;
            for (i = 1; i <= n + 1; i++) {
                if (map[u][i] != 0) {
                    temp = dis[u] + map[u][i];
                    if (temp > dis[i]) {
                        dis[i] = temp;
                        if (!vis[i]) {
                            Q.push(i);
                            vis[i] = 1;
                        }
                    }
                }
            }
        }
    }
    
    int len = 0;
    void traceback() {
        ans[len++] = n + 1;
        vis[n + 1] = 1;
        for (int i = 0; i < len; i++) {
            for (int j = 1; j <= n + 1; j++) {
                if (vis[j] || map[j][ans[i]] == 0) continue;
                if (dis[ans[i]] == dis[j] + map[j][ans[i]]) {
                    ans[len++] = j;
                    vis[j] = 1;
                }
            }
        }
        sort(ans, ans+len);
    }
    
    int main() {
        int m;
        scanf("%d%d", &n, &m);
        int i, j;
        for (i = 1; i <= n + 1; i++) {
            vis[i] = 0;
            dis[i] = 0;
            for (j = 1; j <= n + 1; j++)
                map[i][j] = 0;
        }
        int a, b;
        for (i = 0; i < m; i++) {
            scanf("%d%d", &a, &b);
            scanf("%d", &map[a][b]);
        }
        SPFA();
        traceback();
        printf("%d\n%d", dis[n + 1], ans[0]);
        for (i = 1; i < len; i++)
            printf(" %d", ans[i]);
        return 0;
    }
    
  • 0
    @ 2017-04-18 20:27:09

    状态 耗时 内存占用

    #1 Accepted 4ms 372.0KiB
    #2 Accepted 4ms 256.0KiB
    #3 Accepted 3ms 216.0KiB
    #4 Accepted 3ms 256.0KiB
    #5 Accepted 3ms 384.0KiB
    #6 Accepted 3ms 352.0KiB
    #7 Accepted 3ms 256.0KiB
    #8 Accepted 3ms 328.0KiB
    #9 Accepted 3ms 376.0KiB
    #10 Accepted 3ms 356.0KiB

  • 0
    @ 2016-11-19 19:06:12

    测试数据 #0: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1164 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 1164 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 1164 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 1164 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 1164 KiB, score = 10
    Accepted, time = 0 ms, mem = 1168 KiB, score = 100
    代码
    var n,m,i,x,y,z,j,k:longint;
    a:array[0..300,0..300] of longint;
    begin
    readln(n);
    readln(m);
    fillchar(a,sizeof(a),0);
    for i:=1 to m do
    begin
    read(x,y,z);
    a[x,y]:=z;
    end;
    for k:=1 to n+1 do
    for i:=1 to n+1 do if (i<>k) then
    for j:=1 to n+1 do
    if (a[i,k]+a[k,j]>a[i,j])and(i<>j)and(j<>K)and(a[i,k]<>0)and(a[k,j]<>0) then a[i,j]:=a[i,k]+a[k,j];
    writeln(a[1,n+1]);
    write(1,' ');
    for i:=2 to n do
    if a[1,i]+a[i,n+1]=a[1,n+1] then write(i,' ');
    write(n+1);
    end.
    floyd算法ac。

  • 0
    @ 2016-09-06 14:04:21
    评测状态    Accepted
    题目  P1027 休息中的小呆
    递交时间    2016-09-06 14:02:34
    代码语言    C++
    评测机 ShadowShore
    消耗时间    30 ms
    消耗内存    632 KiB
    评测时间    2016-09-06 14:02:36
    评测结果
    编译成功
    
    测试数据 #0: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 624 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 632 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 628 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 632 KiB, score = 10
    Accepted, time = 30 ms, mem = 632 KiB, score = 100
    代码
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int map[131][131]={0},sum[102],l=1;
    int n,m;
    int main()
    {
        cin>>n>>m;
        for (int i=1;i<=m;i++)
        {
            int a,b,w;
            cin>>a>>b>>w;
            map[a][b] = w;
        }
        for (int k=1;k<=n+1;k++)
            for (int i=1;i<=n+1;i++)
                if (k != i)
                for (int j=1;j<=n+1;j++)
                if (map[i][k] != 0 && map[k][j] != 0 &&i != j && j != k)
                    map[i][j] = max(map[i][j],map[i][k]+map[k][j]);
        cout<<map[1][n+1]<<endl;
        cout<<1<<" ";
        for (int i=2;i<=n;i++)
            if (map[1][i] + map[i][n+1] == map[1][n+1])
            cout<<i<<" ";
        cout<<n+1<<endl;
        return 0;
    }
    

    水水的

    • @ 2016-09-23 20:31:11

      SB一样的Hory,大家别信,这时骗人的~!!!!!!!

    • @ 2016-09-23 20:47:27

      咳咳,我Orz好吧?*唉*

  • 0
    @ 2016-05-19 16:58:35
  • 0
    @ 2014-10-27 11:52:45

    为什么搜索80分……无力check
    var n,m,i,j,k,a,b,c:longint;
    f:array[0..200,0..200] of longint;
    function max(a,b:longint):longint;
    begin
    if a>b then exit(a)
    else exit(b);
    end;

    begin
    readln(n);
    readln(m);
    for i:=1 to m do
    begin
    readln(a,b,c);
    f[a,b]:=c;
    end;
    for k:=1 to n+1 do
    for i:=1 to n+1 do
    if i<>k then
    for j:=1 to n+1 do
    if (j<>k) and (i<>j) then
    if (f[i,k]<>0) and (f[k,j]<>0) then

    f[i,j]:=max(f[i,k]+f[k,j],f[i,j]);
    writeln(f[1,n+1]);
    write(1,' ');
    for i:=2 to n do
    if f[1,i]+f[i,n+1]=f[1,n+1] then
    write(i,' ');
    writeln(n+1);
    end.
    NOIP2014赛前AC留念~~~~~~~~
    为什么只有floyd才能过?
    var n,m,i,j,k,a,b,c:longint;
    f:array[0..200,0..200] of longint;
    function max(a,b:longint):longint;
    begin
    if a>b then exit(a)
    else exit(b);
    end;

    begin
    readln(n);
    readln(m);
    for i:=1 to m do
    begin
    readln(a,b,c);
    f[a,b]:=c;
    end;
    for k:=1 to n+1 do
    for i:=1 to n+1 do
    if i<>k then
    for j:=1 to n+1 do
    if (j<>k) and (i<>j) then
    if (f[i,k]<>0) and (f[k,j]<>0) then

    f[i,j]:=max(f[i,k]+f[k,j],f[i,j]);
    writeln(f[1,n+1]);
    write(1,' ');
    for i:=2 to n do
    if f[1,i]+f[i,n+1]=f[1,n+1] then
    write(i,' ');
    writeln(n+1);
    end.

  • 0
    @ 2013-10-17 10:20:58

    咦?没人和我一样写dfs么..

  • 0
    @ 2013-09-28 17:41:03

    乍一看想起了关键路径……准备拓扑排序……
    忽然一想不是……是FLoyed

  • 0
    @ 2013-03-03 14:53:28

    floyed的确很爽…………
    测试数据 #0: Accepted, time = 78 ms, mem = 940 KiB, score = 10

    测试数据 #1: Accepted, time = 15 ms, mem = 936 KiB, score = 10

    测试数据 #2: Accepted, time = 15 ms, mem = 940 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 940 KiB, score = 10

    测试数据 #4: Accepted, time = 7 ms, mem = 940 KiB, score = 10

    测试数据 #5: Accepted, time = 31 ms, mem = 940 KiB, score = 10

    测试数据 #6: Accepted, time = 7 ms, mem = 936 KiB, score = 10

    测试数据 #7: Accepted, time = 15 ms, mem = 936 KiB, score = 10

    测试数据 #8: Accepted, time = 7 ms, mem = 940 KiB, score = 10

    测试数据 #9: Accepted, time = 15 ms, mem = 940 KiB, score = 10

    Summary: Accepted, time = 190 ms, mem = 940 KiB, score = 100

    代码
    program P1027;
    var
    i,j,k,n,m,x:longint;
    f:array[1..200,1..200] of longint;
    function max(x,y:longint):longint;
    begin
    if x>y then
    max:=x
    else max:=y;
    end;
    procedure floyed;
    begin
    for k:=1 to n+1 do
    for i:=1 to n+1 do
    if k<>i then
    for j:=1 to n+1 do
    if (f[i,k]<>0) and (f[k,j]<>0) and (i<>j) and (j<>k) then
    f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);
    end;
    Begin
    readln(n);
    readln(m);
    for x:=1 to m do
    begin
    readln(i,j,k);
    f[i,j]:=k;
    end;
    floyed;
    writeln(f[1,n+1]);
    write(1);
    for i:=2 to n do
    if (f[1,i]+f[i,n+1]=f[1,n+1]) then
    write(' ',i);
    writeln(' ',n+1);
    end.

  • 0
    @ 2009-11-04 18:21:26
    • -, 这种题目描述也能有环啊..
  • 0
    @ 2009-11-04 11:01:04

    ‘输出数据比标准答案长’的是因为【末尾不得有多余空格】

    ╮(╯▽╰)╭

  • 0
    @ 2009-10-29 19:22:20

    原来FLOYD还可以求最长路

    今天真是长见识了

  • 0
    @ 2009-10-22 21:29:08

    乍一看想起了关键路径……准备拓扑排序……

    忽然一想不是……是FLoyed

信息

ID
1027
难度
4
分类
图结构 点击显示
标签
(无)
递交数
1467
已通过
584
通过率
40%
被复制
8
上传者