题解

120 条题解

  • 11
    @ 2017-05-07 22:19:57
    /*
    嗯典型的最小环问题
    因为n很小可以直接Floyd求最小环
    注意最小环ans更新的位置
    每次枚举k为下家更新点
    应该先尝试更新ans再更新i,j之间的最短路
    我们用g[i][j]来记录i,j之间最短路径
    而w[i][j]用来保存i,j之间的原始路径长度
    因为我们知道i,j要构成一个最小环
    肯定要有两条路可走
    1.直接从i到j。
    2.从i经过某个中途点k到达j
    即对于每一个k 我们先尝试从这个k点对于所有的i,j点能不能得到最小环
    然后我们再用这个k点尝试更新路径
    该算法的证明:
    一个环中的最大结点为K(编号最大),与其相连的两个点为i,j ,
    这个环的最短长度为: g[i][k] + g[k][j] + i到j的路径中所有结点编号都不大于k的最短路径长度,
    根据floyd的原理,在最外层循环做一个k-1次之后,
    g[i][j] 则代表了i到j的路径中所有结点的编号都不大于k的最短路径。
    所以我们枚举的i,j要有
    1<=i<k,i<j<k
    再换一种说法吧
    比普通Floyd多出来的部分,主要利用到的原理是当处理到k时,
    所有以1 到k - 1为中间结点的最短路径都已经确定,
    则这时候的环为(i到j(1 < i, j <= k - 1)的最短路径) + 边(i, k) + 边(k, j)
    遍历所有的i, j找到上述式子的最小值即位k下的最小代价环  
    这样总能懂了吧QAQ
    */
    /*
    路径的求法:
    用一个pre[i][j]记录j前面的一个顶点, 初始化为i,当出现需要更新的时候则将pre[i][j] = pre[k][j];
    若i== j的时候则表示找全了路径,最后将k点加入路径中 
    核心代码:
    While(i != j)
    {  
        if (i != j) 
        {  
            Path[len++] = j;
            J = pre[i][j]; 
        }  
         Path[len++] = i;
    }
    http://wenku.baidu.com/view/c6382a41a8956bec0975e3c0.html?from=related
    http://blog.csdn.net/youngyangyang04/article/details/7054931
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int INF=1e8;
    int w[102][102],g[102][102];
    int n,e;
    
    void init()
    {
        int x,y,v;
        for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    w[i][j]=g[i][j]=INF;
        for(int i=1;i<=e;i++)
        {
            scanf("%d%d%d",&x,&y,&v);
            w[x][y]=w[y][x]=g[x][y]=g[y][x]=v;
        }
    }
    
    void work()
    {
        int ans=INF;
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<k;i++)//最小环
                for(int j=i+1;j<k;j++)//为了避免一条边计算两次并且i == j时因为权重会出错 
                    ans=min(ans,g[i][j]+w[i][k]+w[k][j]);
            for(int i=1;i<=n;i++)//Floyd
                for(int j=1;j<=n;j++)
                    if(i!=j)
                        g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
        }
        if(ans==INF)
            cout<<"No solution."<<endl;
        else
            cout<<ans<<endl;
    }
    
    int main()
    {
        while(scanf("%d%d",&n,&e)!=EOF)
        {
            init();
            work();
        }
    }
    
  • 4
    @ 2017-11-23 13:42:05

    #include<cstdio>
    #define maxn 5010
    #define INF 1<<24
    int dist[maxn][maxn], g[maxn][maxn];
    int n, m;
    void init() {
    for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
    dist[i][j]=g[i][j]=INF;
    int u, v, w;
    for(int i=0; i<m; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    if(dist[u][v]>w) {
    dist[u][v]=dist[v][u]=w;
    g[u][v]=g[v][u]=w;
    }
    }
    }
    void solve() {
    int _min=INF, cnt=0;
    for(int k=1; k<=n; ++k) {
    for(int i=1; i<k; ++i)
    if(g[i][k]^INF)
    for(int j=i+1; j<k; ++j) {
    int tmp=dist[i][j]+g[i][k]+g[k][j];
    if(tmp<_min) {
    _min=tmp;
    cnt=1;
    } else if(tmp==_min) cnt++;
    }
    for(int i=1; i<=n; ++i)
    if(dist[i][k]^INF)
    for(int j=1; j<=n; ++j)
    if(dist[k][j]^INF) {
    int tmp=dist[i][k]+dist[k][j];
    if(tmp<dist[i][j]) dist[i][j]=tmp;
    }
    }
    if(cnt>0) printf("%d\n", _min);
    else printf("No solution.\n");
    }
    int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
    init();
    solve();
    }
    return 0;
    }

  • 3
    @ 2015-03-11 13:03:47

    最小环问题
    <1>朴素的算法:
    令e(u,v)表示u和v之间的连边,再令min(u,v)表示,删除u和v之间的连边之后,u和v之间的最短路
    最小环则是min(u,v) + e(u,v),时间复杂度是EV2。
    <2>改进的方法:
    在floyd的同时,顺便算出最小环
    g[i][j]=(i,j之间的边长)
    dist:=g;
    for k:=1 to n do
    begin
    for i:=1 to k-1 do
    for j:=i+1 to k-1 do
    answer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);
    for i:=1 to n do
    for j:=1 to n do
    dist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);
    end;
    关于算法<2>的证明:
    一个环中的最大结点为k(编号最大),与他相连的两个点为i,j,这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,所有结点编号都小于k的最短路径长度
    根据floyd的原理,在最外层循环做了k-1次之后,dist[i][j]则代表了i到j的路径中,所有结点编号都小于k的最短路径
    综上所述,该算法一定能找到图中最小环。
    #include<stdio.h>
    const long max=1000000;
    long n,m,x,y,d;
    long dist[111][111],map[111][111],ans;
    long min(long a,long b)
    {
    if(a<b) return a;
    else return b;
    }
    int main()
    {
    int i,j,k;
    while(scanf("%ld%ld",&n,&m)!=EOF)
    {
    // ;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++) map[i][j]=max;
    for(i=1;i<=m;i++)
    {
    scanf("%ld%ld%ld",&x,&y,&d);
    map[x][y]=d;
    map[y][x]=d;
    }
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++) dist[i][j]=map[i][j];
    ans=max;
    for(k=1;k<=n;k++)
    {
    for(i=1;i<=k-1;i++)
    for(j=i+1;j<=k-1;j++)
    ans=min(dist[i][j]+map[i][k]+map[k][j],ans);
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    }
    if(ans==max) printf("No solution.\n");
    else printf("%ld\n",ans);
    }
    return 0;
    }

  • 2
    @ 2017-11-23 13:40:28

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    #define maxn 108
    #define INF 1<<24
    int dist[maxn][maxn], g[maxn][maxn];
    int n, m;
    void init(){
    for ( int i=1; i<=n; ++i )
    for ( int j=1; j<=n; ++j )
    dist[i][j] = g[i][j] = INF;
    int u, v, w;
    for ( int i=0; i<m; ++i ) {
    scanf("%d%d%d", &u, &v, &w);
    if(dist[u][v] > w) {
    dist[u][v] = dist[v][u] = w;
    g[u][v] = g[v][u] = w;
    }
    }
    };

    void solve(){
    int minn = INF, cnt=0;
    for ( int k=1; k<=n; ++k ){
    for ( int i=1; i<k; ++i ) if(g[i][k]^INF)
    for( int j=i+1; j<k; ++j ) if(dist[i][j]^INF && g[k][j]^INF)
    {
    int tmp = dist[i][j]+g[i][k]+g[k][j];
    if(tmp < minn ) {
    minn = tmp; cnt=1;
    }else if(tmp == minn) ++cnt;
    }
    for(int i=1; i<=n; ++i ) if(dist[i][k]^INF)
    for(int j=1; j<=n; ++j ) if(dist[k][j]^INF)
    {
    int tmp= dist[i][k]+dist[k][j];
    if(tmp < dist[i][j]) dist[i][j] = tmp;
    }
    }
    if(cnt > 0) printf("%d\n", minn);
    else printf("No solution.\n");
    }

    int main(){
    while(scanf("%d%d", &n, &m)!=EOF){

    init();
    solve();
    }
    return 0;

    }

  • 1
    @ 2017-11-23 13:40:20

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    #define maxn 108
    #define INF 1<<24
    int dist[maxn][maxn], g[maxn][maxn];
    int n, m;
    void init(){
    for ( int i=1; i<=n; ++i )
    for ( int j=1; j<=n; ++j )
    dist[i][j] = g[i][j] = INF;
    int u, v, w;
    for ( int i=0; i<m; ++i ) {
    scanf("%d%d%d", &u, &v, &w);
    if(dist[u][v] > w) {
    dist[u][v] = dist[v][u] = w;
    g[u][v] = g[v][u] = w;
    }
    }
    };

    void solve(){
    int minn = INF, cnt=0;
    for ( int k=1; k<=n; ++k ){
    for ( int i=1; i<k; ++i ) if(g[i][k]^INF)
    for( int j=i+1; j<k; ++j ) if(dist[i][j]^INF && g[k][j]^INF)
    {
    int tmp = dist[i][j]+g[i][k]+g[k][j];
    if(tmp < minn ) {
    minn = tmp; cnt=1;
    }else if(tmp == minn) ++cnt;
    }
    for(int i=1; i<=n; ++i ) if(dist[i][k]^INF)
    for(int j=1; j<=n; ++j ) if(dist[k][j]^INF)
    {
    int tmp= dist[i][k]+dist[k][j];
    if(tmp < dist[i][j]) dist[i][j] = tmp;
    }
    }
    if(cnt > 0) printf("%d\n", minn);
    else printf("No solution.\n");
    }

    int main(){
    while(scanf("%d%d", &n, &m)!=EOF){

    init();
    solve();
    }
    return 0;

    }

  • 0
    @ 2018-02-15 08:01:30
    状态  题目  递交者     时间  内存  语言  递交时间
    Accepted
        P1046 观光旅游  zyc2000     225ms   508.0 KiB   C++     48秒前
    Wrong Answer
        P1046 观光旅游  zyc2000     223ms   512.0 KiB   C++     2分钟前
    Wrong Answer
        P1046 观光旅游  zyc2000     183ms   488.0 KiB   C++     5分钟前
    Wrong Answer
        P1046 观光旅游  zyc2000     267ms   504.0 KiB   C++     8分钟前
    Wrong Answer
        P1046 观光旅游  zyc2000     162ms   512.0 KiB   C++     10分钟前
    Wrong Answer
        P1046 观光旅游  zyc2000     215ms   512.0 KiB   C++     13分钟前
    Wrong Answer
        P1046 观光旅游  zyc2000     289ms   488.0 KiB   C++     16分钟前
    Wrong Answer
        P1046 观光旅游  zyc2000     326ms   480.0 KiB   C++     18分钟前
    Wrong Answer
        P1046 观光旅游  zyc2000     281ms   616.0 KiB   C++     1天前
    Time Exceeded
        P1046 观光旅游  zyc2000     ≥6043ms     ≥384.0 KiB  C++     2周前
    

    统统WA,原因竟是

    No solution. S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!S是小写!

    #include<cstdio>
    #include<iostream>
    #define MAXN 105
    #define INF 100000000
    using namespace std;
    
    int n, m;
    int o[MAXN][MAXN];
    int f[MAXN][MAXN];
    
    int main(){
      int tfrom, tto, tw;
      while(cin >> n >> m){
        for(int i=1; i<=n; i++){
          for(int j=1; j<=n; j++){
            o[i][j] = f[i][j] = INF;
          }
        }
        for(int i=0; i<m; i++){
          cin >> tfrom >> tto >> tw;
          o[tfrom][tto] = o[tto][tfrom] = f[tfrom][tto] = f[tto][tfrom] = min(o[tfrom][tto], tw);
        }
        int gans = INF;
        for(int k=1; k<=n; k++){
          for(int i=1; i<k; i++){
            for(int j=i+1; j<k; j++){
              // if(f[i][j] < INF && o[i][k] < INF && o[k][j] < INF){
                gans = min(gans, f[i][j]+o[i][k]+o[k][j]);
              // }
            }
          }
          for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
              if(i == j) continue;
              f[i][j] = min(f[i][j], f[i][k]+f[k][j]);
            }
          }
        }
        if(gans < INF){
          cout << gans << endl;
        }else{
          cout << "No solution." << endl;
        }
      }
    
      return 0;
    }
    
    
  • 0
    @ 2017-12-10 14:36:09

    //求大神指导下这段代码哪里错了
    #include<iostream>
    #include<algorithm>
    #include<climits>
    using namespace std;
    int main()
    {
    int n,m,i,j,k,dis[110][110];
    while(cin>>n>>m)
    {
    int Min=INT_MAX;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    dis[i][j]=INT_MAX;
    for(i=1;i<=m;i++)
    {
    int temp1,temp2;
    cin>>temp1>>temp2;
    cin>>dis[temp1][temp2];
    }
    for(k=1;k<=n;k++)
    {
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
    if(i!=j&&dis[k][j]<INT_MAX&&dis[i][k]<INT_MAX)
    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    }
    }
    for(i=1;i<=n;i++)
    {
    for(j=1;j<=n;j++)
    {
    if(dis[i][j]<INT_MAX&&dis[j][i]<INT_MAX)
    dis[i][j]+=dis[j][i];
    else
    dis[i][j]=INT_MAX;
    }
    Min=min(Min,*min_element(dis[i]+1,dis[i]+1+n));
    }
    if(Min<INT_MAX)
    cout<<Min<<endl;
    else
    cout<<"No solution."<<endl;
    }
    }

  • 0
    @ 2009-11-07 11:50:10

    chrome果然不能提交

    两次No Complied

    我的通过率啊

  • 0
    @ 2009-11-06 18:50:56

    这题真怪,我开始

    1.fillchar(a,sizeof(a),1); 90分

    2.for i:=1 to n do

    for j:=1 to n do

    a:=100000000;

    Ac..

    百思不得其解。。

    • @ 2013-02-15 15:09:54

      fillchar1的话会出错,我以前就是栽在了那上面(实际上是昨天呵呵)。

    • @ 2013-10-31 16:38:36

      maxlongint过程中会加爆的

  • 0
    @ 2009-11-06 00:08:45

    最小环,就是最小环,不会做!

    那么我就把它背下来呗!

    结果写的时候写错了....

    for k:=1 to n do

    for i:=1 to k-1 do

    for j:=i+1 to k-1 do

    写成了:

    for k:=1 to n do

    for i:=1 to k-1 do

    for j:=1 to k-1 do

    。。。。。

    ---|---|---|---|---|---|---|---|---|

    const maxnum=16843009;

    var

    n,m,r:longint;

    map,f:array[0..100,0..100]of longint;

    procedure main;

    var

    i,a,k,j,b,c:longint;

    begin

    readln(n,m);

    fillchar(map,sizeof(map),1);

    for i:=1 to m do

    begin

    readln(a,b,c);

    map[a,b]:=c;

    map:=c;

    end;

    for i:=1 to n do map:=0;

    f:=map;

    r:=maxnum;

    for k:=1 to n do

    begin

    for i:=1 to k-1 do

    for j:=i+1 to k-1 do

    if f+map[j,k]+map[k,i]f+f[k,j] then

    f:=f+f[k,j];

    end;

    if r

  • 0
    @ 2009-11-03 11:04:05

    交了11次终于过了!!!

    居然不能用IE交题?!

    No solution自动进化成了no solution!

    ……

  • 0
    @ 2009-10-30 10:05:14

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    floyd最小环

  • 0
    @ 2009-10-25 20:52:57

    多谢huyuanming11提醒...

  • 0
    @ 2009-10-20 22:39:59

    Floyd求最小环问题

    Accepted 有效得分:100 有效耗时:725ms

    Sunny和我有仇么?。。今天3个Floyd的程序都这么丑的时间

  • 0
    @ 2009-10-18 10:31:53

    对输入格式描述中的第一句话

    和注释中的第一句话比较无语.

    做法楼下的牛们已经说得很清楚了

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 72ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 72ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 25ms

    ├ 测试数据 10:答案正确... 134ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:303ms

  • 0
    @ 2009-10-04 18:27:53

    终于AC了......

    注意inf = 1000000000 会爆

    原因(我猜想的):

    在普通Floyed中

    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

    inf = 1e9没有任何问题,因为int上限大于2e9

    而在Floyed改进算法中,

    ans = min(ans, d[i][k] + d[k][j] + g[i][j]);

    如果3个加数都是inf, 和就是3e9,int就爆了......

    所以,保险起见,inf = 1e8

  • 0
    @ 2009-09-23 18:27:13

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    交了N遍才过。。。原来读入的时候要用readln……终于明白了……

    但是

    这是一种怎样的floyed改进?

  • 0
    @ 2009-09-18 13:13:36

    莫名其妙 max:=1000000000 就80

    设成100000000 就AC 数据有问题

  • 0
    @ 2009-09-16 20:19:45

    program p1046;

    var a,f:array[1..100,1..100] of longint;

    i,j,k,l,m,n,p,q,r,max:longint;

    begin

    while not eof do begin

    fillchar(a,sizeof(a),0);

    readln(n,m);

    for i:=1 to n do

    for j:=1 to n do a:=10000000;

    for i:=1 to m do

    begin readln(p,q,r);a[p,q]:=r;a[q,p]:=r; end;

    for i:=1 to n do a:=0;f:=a;max:=10000000;

    for k:=1 to n do begin

    for i:=1 to k-1 do

    for j:=i+1 to k-1 do

    if f+a+a[k,j]

  • 0
    @ 2009-09-16 15:37:30

    Floyed求最小环,发个程序,下面的讲的太抽象.

    Const Maxn=100;

    INF=1000000;

    Var matrix,f:array[1..Maxn,1..Maxn]of longint;

    n,m:longint;

    Procedure readp;

    var i,u,v,t:longint;

    begin

    readln(n,m);

    filldword(matrix,sizeof(matrix)div 4,INF);

    for i:=1 to m do begin

    readln(u,v,t);

    matrix:=t;

    matrix[v,u]:=t;

    end;

    for i:=1 to n do

    matrix:=0;

    f:=matrix;

    end;

    Procedure solve;

    var i,j,k,ans:longint;

    begin

    ans:=INF;

    for k:=1 to n do begin

    for i:=1 to k-1 do

    for j:=i+1 to k-1 do

    if f+matrix+matrix[k,j]

信息

ID
1046
难度
6
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
4406
已通过
1185
通过率
27%
被复制
1
上传者