Codeforces 893 Rumor 并查集/DFS-白红宇

Codeforces 893 Rumor 并查集/DFS

阅读量：6584 次

发布时间：2019-06-24

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

　　题目链接： http://codeforces.com/contest/893/problem/C

　　题目描述：你可以收买每一个人，收买他之后相当于收买了他所有的朋友(双向的)，问最少多少钱可以收买到所有人。

　　解题思路：典型的并查集，自己看到这题就知道该怎么做，无奈没有学习过图论，就拿DFS做的， T掉了，因为我很多重复的边都存进去了，然后看别人的博客又学习到了新的姿势

　　代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;const int maxn = 1e5+10;int a[maxn];const int INF = 0x3fffffff;int n, d;int main() { scanf("%d%d", &n, &d); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } int flag = 1; int top, bottom; int res = 0; top = bottom = 0; for(int i = 0; i < n; i++) { if(a[i] == 0) { if(top < 0) { res++; top = d; } bottom = max(0, bottom); } else { top += a[i]; bottom += a[i]; top = min(top, d); if(bottom > d) { flag = -1; break; } } } if(flag == 1) { printf("%d\n", res); } else { printf("-1\n"); } return 0;}

View Code

　　思考：自己没有图论的经验是真的伤，我一直在害怕图论不知道为什么，所以打算学习图论了， ACM还是不想弃啊，痛苦是痛苦，但是对于自己算法能力和编程能力的提高却是真的，为了走工程而放弃了自己坚持了一年多的ACM是不是太没有远见了？

转载于:https://www.cnblogs.com/FriskyPuppy/p/7911276.html

你可能感兴趣的文章