HDU 3832 Earth Hour（最短路）-白红宇

HDU 3832 Earth Hour（最短路）

阅读量：6934 次

发布时间：2019-06-27

本文共 1277 字，大约阅读时间需要 4 分钟。

题目地址：

这个题的这种方法我无法给出证明。

我当时这个灵感出来的时候是想的是要想覆盖的点最少，那就要尽量反复利用这些点，然后要有两个之间是通过还有一个点间接连接的，这样会充分利用那些点。

然后就这样写了一次，一直WA。。然后中午睡觉的时候突然想到了有一种情况这样做是不正确的。那就是有个点作为中间点，与三个点相连的情况，这样的情况尽管也符合。可是会有反复边。。。

可是恰恰相反。。反复边应该越多越好。

。

那就充分利用了这些点。那么这个点应该怎么找呢？那就直接枚举好了。可是枚举每一个点都求一次最短路的话非常明显不科学。。

反正仅仅是利用到那三个点的最短距离，那就仅仅对这三个点分别求一次，那别的点到这三个点的最短路就都求出来了。

然后枚举全部点到三个点的距离之和，找出最小的。再用n减去最小值就是须要关闭的最大值了。

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include
             
              using namespace std;const int INF=0x3f3f3f3f;int head[300], cnt, vis[300];int d[3][301];struct node1{ int x, y, r;} dian[1000000];struct node{ int u, v, w, next;} edge[1000000];void add(int u, int v, int w){ edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;}void spfa(int source, int x){ memset(d[x],INF,sizeof(d[x])); memset(vis,0,sizeof(vis)); d[x][source]=0; deque
              
               q; q.push_back(source); while(!q.empty()) { int u=q.front(); q.pop_front(); vis[u]=0; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(d[x][v]>d[x][u]+edge[i].w) { d[x][v]=d[x][u]+edge[i].w; if(!vis[v]) { vis[v]=1; if(!q.empty()&&d[x][v]
               
                d[0][i]+d[1][i]+d[2][i]+1) { min1=d[0][i]+d[1][i]+d[2][i]+1; } } } printf("%d\n",n-min1); } return 0;}

转载地址：http://qdmjl.baihongyu.com/

你可能感兴趣的文章