beloved_ACM

SB，NB，都是一个B.
posts - 29, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

ZOJ——2760——HOW many shortest path

Posted on 2010-10-08 22:09 成幸毅 阅读(363) 评论(0)  编辑 收藏 引用
  题目的意思是要求都多少边不重合的最短路。可以先用一个二重循环算出哪些边在可在最短路中，然后给他们赋值容量1，然后再从求个最大流就好了。下面给出计算哪些边在最短路径中的代码。
void floyd() {
   
   for(int k = 0; k < n; k++) 
      for(int i = 0; i < n; i++) 
         if(d[i][k] != INF ) 
            for(int j = 0; j < n; j++) {
               if(d[k][j] != INF) {
                   if(d[i][j] > d[k][j] + d[i][k]) {
                      d[i][j] = d[k][j] + d[i][k];
                   } 
               }
            }
   
   for(int i = 0; i < n; i++)
      if(d[s][i] != INF)
         for(int j = 0; j < n; j++) {
           if(d[j][t] != INF)
            if(mat[i][j] != -1 ){
               if(d[s][t] == d[s][i] + mat[i][j] + d[j][t]) {
                 c[i][j] = 1;
               }
            }
         } 
    
} 

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