POJ 3723 解题报告-白红宇

POJ 3723 解题报告

阅读量：4204 次

发布时间：2019-05-26

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

这道题是最小生成树问题。由于“收集”每个人只能用一次“关系”，所以利用的关系不能形成环。贪心从最小的关系开始，只要不能形成环就收集。这就是kruskal用并查集的算法。最后没收集的人每人按最大代价加入总代价就可以了。

Accepted

908K

344MS

2132B

/* ID: thestor1 LANG: C++ TASK: poj3723 */#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;const int MAXR = 50000;const int MAXN = 10000;const int MAXM = 10000;void makeset(const int N, int parent[], int rank[]){ for (int u = 0; u < N; ++u) { parent[u] = u; rank[u] = 0; }}int find(int u, int parent[]){ if (parent[u] != u) { parent[u] = find(parent[u], parent); } return parent[u];}void union_set(int u, int v, int parent[], int rank[]){ int ru = find(u, parent); int rv = find(v, parent); if (ru == rv) { return; } if (rank[ru] < rank[rv]) { parent[ru] = rv; } else if (rank[rv] < rank[ru]) { parent[rv] = ru; } else { parent[ru] = rv; rank[rv]++; }}class Edge{public: int u, v, w; Edge() {} Edge(int u, int v, int w) : u(u), v(v), w(w) {} bool operator< (const Edge &rhs) const { if (this->w != rhs.w) { return this->w < rhs.w; } return this->u < rhs.u || (this->u == rhs.u && this->v < rhs.v); }};int kruskal(int parent[], int rank[], const int N, Edge edges[], const int M, int &collected){ makeset(N, parent, rank); sort(edges, edges + M); int mst = 0; for (int i = 0; i < M; ++i) { Edge edge = edges[i]; if (find(edge.u, parent) != find(edge.v, parent)) { collected++; mst += edge.w; union_set(edge.u, edge.v, parent, rank); } } return mst;}int main(){ int parent[MAXN + MAXM]; int rank[MAXN + MAXM]; Edge edges[MAXR]; int T; scanf("%d", &T); int N, M, R; int xi, yi, di; for (int t = 0; t < T; ++t) { scanf("%d%d%d", &N, &M, &R); for (int r = 0; r < R; ++r) { scanf("%d%d%d", &xi, &yi, &di); edges[r].u = xi; edges[r].v = N + yi; edges[r].w = 10000 - di; } int collected = 0; int mst = kruskal(parent, rank, N + M, edges, R, collected); int minimumPay = mst + (N + M - collected) * 10000; printf("%d\n", minimumPay); } return 0;}

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

你可能感兴趣的文章