posts - 14,  comments - 11,  trackbacks - 0
题目大意:
   去掉给定的边,看每一个点是否能从别的点到达!
    如果能够到达,则求出对于每一个点到其他所有的点最短距离之和,将这些和相加就是最后的结果

   解题思路:
      对每一个点求一次单源最短路,然后求和,相加的到最后的结果……
      但,算一下时间复杂度: 复杂度是O(M*N*M)。由于M*N*M=3000*100*3000=9*108,不可能AC

      所以,需要我们另辟他径。网上有说建什么最短路径树,这个我不懂……
      我的思路是:引用前面的思路,对每一个点求一次最短路,并将其求和,保存在一个数组里头,定为sum[i],i表示着一个点到所有其他点最短路之和。并将这些和相加 ans = sum[1]  + …… + sum[n]; 
      然后,删除一条边,其顶点暂定为u,v,对这条边的一个顶点u在一次求最短路,如果这个点,不能到达这条边的另一个点v,则 直接输出INF
      如果,能够到达,则对v也求一次最短路,对于u,v两点来说,求得u到每一个点的最短路之和sum_u,求得v到每一个点的最短路之和sum_v,
      最后结果为: ans = ans + sum_u + sum_v - sum[u] - sum[v];
      ans为最后答案(千万记住是每一组的,因为有m条边)
      具体看代码:
http://acm.hdu.edu.cn/showproblem.php?pid=2433
时间是 953ms
         
  1 #include <iostream>
  2 #include <queue>
  3 using namespace std;
  4 const int SIZE = 102;
  5 const int INF = 1 << 30;
  6 struct node
  7 {
  8        int v, w, next;
  9 }map[SIZE * SIZE];
 10 
 11 int head[SIZE], use;
 12 int num[SIZE * 30];
 13 int sum[SIZE];
 14 
 15 void add(int u, int v, int w)
 16 {
 17      map[use].v = v;
 18      map[use].w = w;
 19      map[use].next = head[u];
 20      head[u] = use ++;
 21 }
 22 void init()
 23 {
 24      use = 0;
 25      memset(head, -1sizeof(head));
 26      memset(sum, 0sizeof(sum));
 27 }
 28 
 29 queue <int> q;
 30 bool vist[SIZE];
 31 int dis[SIZE];
 32 
 33 int spfa(int s)
 34 {
 35      while (!q.empty()) q.pop();
 36      
 37      for (int i = 0; i < SIZE ; i ++)  dis[i] = INF;
 38      
 39      memset(vist, falsesizeof(vist));
 40      dis[s] = 0;
 41      vist[s] = true;
 42      q.push(s);
 43      int ans = 0;
 44      while (!q.empty()) 
 45      {
 46            int u = q.front();
 47            q.pop();
 48            vist[u] = false;
 49            ans += dis[u];
 50            for (int i = head[u]; i != -1; i = map[i].next)
 51            {
 52                int v = map[i].v;
 53                if (dis[v] > dis[u] + map[i].w)
 54                {
 55                   dis[v] = dis[u] + map[i].w;
 56                   if (!vist[v])
 57                   {
 58                      vist[v] = true;
 59                      q.push(v);
 60                   }
 61                }
 62            }
 63      }
 64      return ans;
 65 }
 66 int main()
 67 {
 68      int n, m;
 69      while (scanf("%d%d"&n, &m) != EOF)
 70      {
 71            int i, j, k;
 72            int u, v;
 73            init();
 74            memset(num, 0sizeof(num));
 75            for (i = 1; i <= m; i++)
 76            {
 77                scanf("%d%d"&u, &v);
 78                num[i] = use;
 79                add(u, v, 1);
 80                add(v, u, 1);
 81            }
 82            int ans = 0;
 83            for (i = 1; i <= n; i++)  
 84            {
 85                sum[i] = spfa(i);
 86                ans += sum[i];
 87            }
 88            int tmp = ans;
 89            for (i = 1; i <= m; i++)
 90            {
 91                map[num[i]].w = INF;
 92                map[num[i]^1].w = INF;
 93                
 94                ans = tmp;
 95                ans += spfa(map[num[i]].v);
 96                
 97                if (dis[map[num[i]^1].v] == INF) 
 98                {
 99                   printf("INF\n");
100                }
101                else 
102                {
103                     ans += spfa(map[num[i]^1].v);
104                     ans = ans - sum[map[num[i]].v] - sum[map[num[i]^1].v];
105                     printf("%d\n", ans);
106                }
107                map[num[i]].w = 1;
108                map[num[i]^1].w = 1;
109            }
110      }
111 return 0;
112 }
113 

   
posted on 2012-03-09 15:35 路修远 阅读(1803) 评论(8)  编辑 收藏 引用 所属分类: 路修远

FeedBack:
# re: HDU 2433 最短路
2012-09-22 10:29 | ff
这样貌似不对啊啊  回复  更多评论
  
# re: HDU 2433 最短路
2012-09-22 10:47 | 路修远
要不在看看有什么地方不同 ?@ff
  回复  更多评论
  
# re: HDU 2433 最短路
2012-09-22 10:50 | 路修远
不知道你说的是哪里有问题 ,能不能指出来 咯? @ff
  回复  更多评论
  
# re: HDU 2433 最短路
2012-12-03 21:20 | attacker
你这样可以AC????删除<U,V>不仅改变 u,v最短路啊、、、求解  回复  更多评论
  
# re: HDU 2433 最短路
2012-12-04 10:56 | 路修远
@attacker
the i-th line is the new SUM after the i-th road is destroyed  回复  更多评论
  
# re: HDU 2433 最短路
2013-01-04 19:56 |
ans = ans + sum_u + sum_v - sum[u] - sum[v],
这个公式不是很理解啊,不知道博主怎么想的啊,谢谢咯  回复  更多评论
  
# re: HDU 2433 最短路
2013-04-28 19:38 | test
这方法应该不对。 看下面这组数据
4 4
1 2
2 3
3 4
2 4

画个图,删去最后一条边 2 4 后的结果应该是20,但是此方法的输出是19   回复  更多评论
  
# re: HDU 2433 最短路
2014-08-23 17:21 | YueYueZha
@test
的确这组数据应该输出20的  回复  更多评论
  

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


<2012年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

转载,请标明出处!谢谢~~

常用链接

留言簿(1)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

  • 1. re: HDU 2433 最短路
  • @test
    的确这组数据应该输出20的
  • --YueYueZha
  • 2. re: HDU 2433 最短路
  • 这方法应该不对。 看下面这组数据
    4 4
    1 2
    2 3
    3 4
    2 4

    画个图,删去最后一条边 2 4 后的结果应该是20,但是此方法的输出是19
  • --test
  • 3. re: HDU 2433 最短路
  • ans = ans + sum_u + sum_v - sum[u] - sum[v],
    这个公式不是很理解啊,不知道博主怎么想的啊,谢谢咯
  • --姜
  • 4. re: HDU 2433 最短路
  • @attacker
    the i-th line is the new SUM after the i-th road is destroyed
  • --路修远
  • 5. re: HDU 2433 最短路
  • 你这样可以AC????删除<U,V>不仅改变 u,v最短路啊、、、求解
  • --attacker

阅读排行榜

评论排行榜