hiho#1515 - 分数调查(带权并查集的经典应用)


http://www.voidcn.com/article/p-hlsdlkgy-bbz.html
小Hi的学校总共有N名学生,编号1-N。学校刚刚进行了一场全校的古诗文水平测验。
学校没有公布测验的成绩,所以小Hi只能得到一些小道消息,例如X号同学的分数比Y号同学的分数高S分。
小Hi想知道利用这些消息,能不能判断出某两位同学之间的分数高低?
输入
第一行包含三个整数N, M和Q。N表示学生总数,M表示小Hi知道消息的总数,Q表示小Hi想询问的数量。
以下M行每行三个整数,X, Y和S。表示X号同学的分数比Y号同学的分数高S分。
以下Q行每行两个整数,X和Y。表示小Hi想知道X号同学的分数比Y号同学的分数高几分。
对于50%的数据,1 <= N, M, Q <= 1000
对于100%的数据,1 <= N, M, Q<= 100000 1 <= X, Y <= N -1000 <= S <= 1000
数据保证没有矛盾。
输出
对于每个询问,如果不能判断出X比Y高几分输出-1。否则输出X比Y高的分数。
样例输入
10 5 3  
1 2 10  
2 3 10  
4 5 -10  
5 6 -10  
2 5 10  
1 10  
1 5  
3 5
样例输出
-1  
20  
0
很简单的带权并查集,
注意之所以可以在递归回溯过程中采用dis+=,是因为并查
集的路径压缩,不会导致某个点到根结点的权值重复叠加。union的过程很是巧妙。

  学生a比学生b的分数高,可视为 b 是 a的父亲,a的权值为 v , 同理,假如c比b分数高,则b是c的父亲。 如果此时d比c的分数高,但是d不在并查集内,就把d加入并查集,因为d分数比c高,则箭头应该d->c,但是c的父亲是b,则d->b,即d的父亲是b。
  如果两位同学不在同一并查集中,就不能判断。否则能判断,输出 a的权值和b的权值之差。

const int INF = 100000 + 4;
typedef long long LL;
LL dis[INF];
int n, m, q;
LL fa[INF];

void init() {
    for(int i = 1; i <= n; i++) {
        dis[i] = 0;
        fa[i] = i;
    }
}

LL Find(LL x) {
    if(fa[x] == x) {
        return x;
    }
    int t = fa[x];
    fa[x] = Find(fa[x]);
    dis[x] += dis[t];
    return fa[x];
}

void Union(LL x, LL y, LL tx, LL ty, LL d) {
    fa[ty] = tx;
    dis[ty] = dis[x] + d - dis[y];
}

int main() {
    while(~scanf("%d%d%d", &n, &m, &q)) {
            init();

        for(int i = 1, x, y, z; i <= m; i++) {
            scanf("%d%d%d", &x, &y, &z);
            LL tx = Find(x);
            LL ty = Find(y);
            if(tx != ty) {
                Union(x, y, tx, ty, z);
            }
        }

        for(int i = 0, x, y; i < q; i++) {
            scanf("%d%d", &x, &y);
            if(Find(x) == Find(y)) {
                printf("%d\n", dis[y] - dis[x]);
            } else {
                printf("-1\n");
            }

        }

    }
    return 0;
}
https://www.cnblogs.com/mjtcn/p/9755169.html
 2 如果把每个人抽象成一个点,之间的关系抽象成边。
 3 那么如果询问的两个人之间存在关系,说明,他们在图上上是联通的。
 4 所以并查集维护一下连通性。
 5 对于分数之间的关系,用到带权并查集。
 6 每个点里存一个val表示当前点的分数-根节点的分数。
 7 查询:
 8 xy不连通,输出-1,
 9 否则val[x]=fen[x]-fen[u],val[y]=fen[y]-fen[u],输出fen[x]-fen[y]=val[x]-val[y]
10 合并:
11 x的根节点为u,y的根节点为v,fa[u]=v;
12 更新后的val[u]=fen[u]-fen[v],
13 val[x]=fen[x]-fen[u]  ->  fen[u]=fen[x]-val[x]
14 val[y]=fen[y]-fen[v]  ->  fen[v]=fen[y]-val[y]
15 fen[u]-fen[v] = fen[x] - fen[y] + val[y] - val[x] = S + val[y] - val[x]
16 */
int par[maxn],N,M; int sum[maxn];//sum[i]表示i到i的父结点的距离,即i的父结点比i高的分数 void init() { for(int i=0;i<=N;i++) par[i]=i; memset(sum,0,sizeof(sum)); } int find(int x) { if(par[x]!=x) { int tmp=par[x]; par[x]=find(par[x]); sum[x]+=sum[tmp]; } return par[x]; } void unit(int x,int y,int v) { int fx=find(x),fy=find(y); if(fx==fy)//在一棵树上 { return ; } else { par[fx]=fy; sum[fx]=sum[y]-sum[x]-v; } return ; } bool same(int x,int y) { return find(x)==find(y); } int main() { int q; while(~scanf("%d%d%d",&N,&M,&q)) { init(); while(M--) { int x,y,v; scanf("%d%d%d",&x,&y,&v); unit(x,y,v); } while(q--) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",same(x,y)?sum[y]-sum[x]:-1); } } return 0; }


同样使用带权并查集,用数组p记录同学们的权值(与根的分数差),那么路径压缩时,p[a] = p[a] + p],合并时,p[rb] = p[a] + S - p[b]

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts