Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3613 Cow Relays---Floyd+矩阵相乘

Posted on 2011-05-02 17:39 Uriel 阅读(753) 评论(0)  编辑 收藏 引用 所属分类: POJ图论

这是在DY大牛第六期专题里列出的题目之一.

话说搞ACM也2年多了, 竟然用矩阵乘法+Floyd的题目都还没有做过... 上周的组队赛遇到一道题才听说... (没有拜读matrix67的神文... 检讨下... )

/*
POJ 3613 Cow Relays

-------Classify: Floyd+矩阵乘法
----Description: 求从S到T恰好经过K条边(可重复走)的最短路
-----------------K<=1e6, m<100(边数)
---Sample Input:

2 6 6 4----------//K m s t
11 4 6-----------//length x<->y
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

--Sample Output:

10

-----Time Limit: 1000Ms
---------Source: USACO 2007 November Gold
-------Solution: 

    By Solution Report

    01邻接矩阵A的K次方C=A^K,C[i][j]表示i点到j点正好经过K条边的路径数

          对应于这道题,对邻接图进行K次floyd之后,C[i][j]就是点i到j正好经过K条边的最短路


---------Status: AC C++ 532Ms
-----------Date: 2011.05.02
------Reference: 
http://hi.baidu.com/aconly/blog/item/23fb73acc1d874004b36d634.html
-----------Code: 
*/


#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#define N 1010
#define INF 0x3f3f3f3f
typedef 
int M[N][N];

int k, m, s, t, v;
int ans[N][N], adj[N][N], vis[N], vtx[N], dis[N][N], tp[N][N];

void floyd(M c, M a, M b) {
    
int i, j, k;
    
for (k = 0; k < v; ++k)
        
for (i = 0; i < v; ++i)
            
for (j = 0; j < v; ++j)
                
if (c[vtx[i]][vtx[j]] > a[vtx[i]][vtx[k]] + b[vtx[k]][vtx[j]])
                    c[vtx[i]][vtx[j]] 
= a[vtx[i]][vtx[k]] + b[vtx[k]][vtx[j]];
}


void copy(M a, M b) {
    
int i, j;
    
for (i = 0; i < v; ++i)
        
for (j = 0; j < v; ++j) {
            a[vtx[i]][vtx[j]] 
= b[vtx[i]][vtx[j]];
            b[vtx[i]][vtx[j]] 
= INF;
        }

}


void BS(int k) {
    
while (k) {
        
if (k & 1{
            floyd(dis, ans, adj);
            copy(ans, dis);
        }

        floyd(tp, adj, adj);
        copy(adj, tp);
        k 
>>= 1;
    }

}


int main() {
    
int i, j, x, y, w;
    scanf(
"%d %d %d %d"&k, &m, &s, &t);
    
for (i = 0; i <= 1001++i) {
        
for (j = 0; j <= 1001++j) {
            adj[i][j] 
= INF;
            tp[i][j] 
= INF;
            dis[i][j] 
= INF;
            ans[i][j] 
= INF;
        }

        ans[i][i] 
= 0;
    }

    v 
= 0;
    memset(vis, 
0sizeof(vis));
    
for (i = 0; i < m; ++i) {
        scanf(
"%d %d %d"&w, &x, &y);
        
if (!vis[x]) {
            vis[x] 
= 1;
            vtx[v
++= x;
        }

        
if (!vis[y]) {
            vis[y] 
= 1;
            vtx[v
++= y;
        }

        
if (adj[x][y] > w)
            adj[x][y] 
= adj[y][x] = w;
    }

    BS(k);
    printf(
"%d\n", ans[s][t]);
    
return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理