The Way Through The Forest

Toolbox: Dijkstra's Shortest Path Algorithm What is it? Dijkstra's is a shortest path algorithm especially optimized for sparse graphs. Code? Optimized (+ priority queue - needs <queue>) struct value {     int dat, val; constexpr bool operator<( const value& rhs) const { return val > rhs.val; } }; priority_queue<value> pq; vector<value> elist[805]; void dj(int st) {     memset(tmp, 63, sizeof tmp);     tmp[st] = 0;     pq.push({st, 0});     while(!pq.empty())     {         value u = pq.top(); pq.pop();         if(tmp[u.dat] != u.val) continue;         for(value x:elist[u.dat]) // if C++11 incomaptible, change         {             int alt = u.val + x.val;             if(alt < tmp[x.dat]) { tmp[x.dat] = alt; pq.push({x.dat, alt}); }         }     } } Explanation? Dependencies <vector>, <queue> C++ 11 or above st, starting point Edge list in elist Outputs tmp, ar

USACO Training: Sweet Butter "butter" Original Problem Statement Sweet Butter Greg Galperin -- 2001 Farmer John has discovered the secret to making the sweetest butter in all of Wisconsin: sugar. By placing a sugar cube out in the pastures, he knows the N (1 <= N <= 500) cows will lick it and thus will produce super-sweet butter which can be marketed at better prices. Of course, he spends the extra money on luxuries for the cows. FJ is a sly farmer. Like Pavlov of old, he knows he can train the cows to go to a certain pasture when they hear a bell. He intends to put the sugar there and then ring the bell in the middle of the afternoon so that the evening's milking produces perfect milk. FJ knows each cow spends her time in a given pasture (not necessarily alone). Given the pasture location of the cows and a description of the paths that connect the pastures, find the pasture in which to place the sugar cube so that the total distance walked by the cows

RQNOJ 600: Criminals Original Problem Statement 题目描述 S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。 每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。 在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？ 【输入输出样例说明】 罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512（由2 号和3 号罪犯引发）。其他任何分法都不会比这个分法更优。 【数据范围】 对于30%的数据有N≤ 15。 对于70%的数据有N≤ 2000，M≤ 50000。 对于100%的数据有N≤ 20000，M≤ 100000。 输入格式 输入文件的每行中两个数之间用一个空格隔开。 第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。 接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨 气值为cj。数据保证1<aj=<=bj<=N ，0 < cj≤ 1,000,000,000，且每对罪犯组合只出现一 次。 输出格式 共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。 My Interpretation N people are to be separated into two

POJ 1182: Food Chain Problem Statement 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。  现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。  有人用两种说法对这N个动物所构成的食物链关系进行描述：  第一种说法是"1 X Y"，表示X和Y是同类。  第二种说法是"2 X Y"，表示X吃Y。  此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。  1） 当前的话与前面的某些真的话冲突，就是假话；  2） 当前的话中X或Y比N大，就是假话；  3） 当前的话表示X吃X，就是假话。  你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。  Interpretation There are 3 types of animals - A, B, and C. A eats B, B eats C, and C eats A. A person tells you K statements about N animals. There are 2 types of facts, in this format: 1 X Y - Animal X and Animal Y are the same type 2 X Y - Animal X EATS Animal Y You are to count how many lies there are. A statement is a lie when it meets at least one of these criteria: X or Y is bigger than N (there is no such animal) X is said to eat itself It contradicts with a previous statement that's not a lie Spec

Toolbox: Disjoint Sets What is it? The disjoint set is a data structure to efficiently implement and run commands to merge sets. They also efficiently implement checking if two items are in the same set without checking the whole set. However, this data structure becomes inefficient when we need to remove nodes. Code? int N; class DSSet { private:     int rt[MAXN]; public:     DSSet()     {         for(int i=0; i<N; i++) rt[i] = -1;     }     int root(int n)     {         if(rt[n] < 0) return n;         return (rt[n] = root(rt[n]));     }     void merge(int m, int n)     {         int rm = root(m), rn = root(n);         if(rm == rn) return;         if(rt[rm] > rt[rn]) swap(rm, rn);         rt[rm] += rt[rn];         rt[rn] = rm;     }     int size(int n)     {         return -rt[root(n)];     } }; Explanation? This class is called DSSet. A global variable, N, describes how large the set should be, and should

USACO January 2018 - MooTube Problem Statement In his spare time, Farmer John has created a new video-sharing service, which he names MooTube. On MooTube, Farmer John's cows can record, share, and discover many amusing videos. His cows already have posted  N  videos ( 1 ≤ N ≤ 100 , 000 ), conveniently numbered  1 … N . However, FJ can't quite figure out how to help his cows find new videos they might like. FJ wants to create a list of "suggested videos" for every MooTube video. This way, cows will be recommended the videos most relevant to the ones they already watch. FJ devises a metric of "relevance," which determines, as the name suggests, how relevant two videos are to each other. He picks  N − 1  pairs of videos and manually computes their pairwise relevance. Then, FJ visualizes his videos as a network, where each video is a node and the  N − 1  pairs of videos he manually considered are connected. Conveniently, FJ has picked his  N − 1   pair