HDU 2480 Steal the Treasure （并查集+贪心）-白红宇

HDU 2480 Steal the Treasure （并查集+贪心）

阅读量：6163 次

发布时间：2019-06-21

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

题意：给你n个点，m条边，包括有向边与无向边，每条边都有一个权值。在每个点上都有一个人，他可以走与这个点直接相连的所有边中任意一条边一次，并且得到这个权值，就不能走了，注意这条路也只能被一个人走。问最大的权值和是多少

首先我们可以想到每个点直接走与其相连权值最大的可以走的点，不一定是最优的，因为可能：1双向走到2权值为7,1单向走到3权值为6，这时1走到3才是最优的。但是我们可以观察得到对于单向边，我们确定起点，对于双向边，我们可以寻找两个点中最优的一个点，按照这样贪心就可以。

首先我们按照权值排序，还有就是我们要记录这个点是否被用过，但是根据之前的想法，我们可以知道有些时候不能马上确定点，但是可以确定两点找一个。因此我们可以标记0代表没用过，1代表两个点中取一个点（其实是x个点中取x-1个点），2代表已经使用。因此我们可以想到对于单向边，确定点值为2。出现双向边，如果是（0 0）（0 1）我们只能确定为（1 1），但是出现（1 1）（0 2）（1 2）确定点值为（2 2）。（这儿有个小bug）

现在我们要注意几个问题，首先就是如果点1点2是双向边，点2点3是双向边，则我们就要在点1点2点3 中选两个点，所以需要并查集维护连通块，接着如果出现点1点2，点3点4，再出现点2点3，则我们就要维护两个连通块合并。最后我们可以每次都加上这个权值，再判断如果不能加这条边时就减去这个权值，这样并查集就不需要存权值了

通过这个题我学到了，如果我们得到的多个值暂时不能确定那个值是最优的，那么我们可以先假设每个点都是最优的再存下来，接着根据后面的条件解决这个问题

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x
                 
                   0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))
                  
                   >b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=1010;const int Max2=1000100;struct node{ int u,v,d,c;} edg[Max2];int fat[Max],vis[Max];//缩点存不确定的点 标记0 1 2void Init(int n){ for(int i=0; i
                   
                    p2.c;}int Union(int x,int y,int v)//此两点不确定，进行并查集的合并{ int x1=Find(x); int y1=Find(y); if(x1==y1) return 0; fat[x1]=y1; vis[x]=vis[y]=1; return 1;}void Jud(int n,int x){ if(vis[x]==0)//注意 { vis[x]=2; return; } int x1=Find(x); for(int i=1; i<=n; ++i) { if(Find(i)==x1) vis[i]=2; } return;}int Solve(int n,int m){ int ans=0; sort(edg,edg+m,cmp); for(int i=0; i

转载于:https://www.cnblogs.com/zhuanzhuruyi/p/5898127.html

你可能感兴趣的文章