1. Maximum food chain count

For A and B in each group of data, establish directed edges A → B, and finally construct A directed acyclic graph Now it is required to find the sum of the number of points with 0 (i.e. not being preyed by any creature) that can be reached from any point with 0 (i.e. not preying on any creature)

For any starting point, it is necessary to find the number of paths that can reach the end point that meets the conditions. I have successfully solved this problem with search when the data is very small. The data of this problem should be memorized, which is counting DP

Imagine a point 1 where a total of several paths can reach it directly:

 

Then the number of paths to reach point 1 is the sum of the number of paths to reach points 2, 3 and 4

Therefore, by traversing from the starting point to the end point in some way, we can finally get the number of paths to any end point Do you think this way is related to topological sorting? Traversing according to the topological order can make the points similar to 2, 3 and 4 in the figure above always traverse before 1. In the initial state, the number of paths from the starting point to itself is of course 1

The queue is used for processing. The points with an in degree of 0 are placed in the queue for initialization. If it is found that it is the end point (i.e. the out degree of 0) during the processing, it will be added to the answer

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MOD = 80112002;

vector<int> s[5010];
queue<int> q;
int n, m, ru[5010], chu[5010], ct[5010];
int ans;

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        s[x].push_back(y);
        ru[y]++, chu[x]++;
    }

    for(int i = 1; i <= n; i++)
        if(!ru[i]) q.push(i), ct[i] = 1;

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        if(!chu[cur]){
            ans = (ans + ct[cur]) % MOD;
            continue;
        }

        for(auto i : s[cur]){
            ct[i] = (ct[i] + ct[cur]) % MOD;
            ru[i]--;
            if(!ru[i]) q.push(i);
        }
    }

    printf("%d\n", ans);

    return 0;
}

 2. Chores

 

(there is a bug solution to this problem. See the solution area of Luogu problem, which is not discussed here)

If the preparation work of chore A is recorded as chore B is recorded as directed edge a → B, since the preparation work of chore K is always in 1~k-1, a directed acyclic graph will be constructed finally

Chores can always be carried out after all its preparations are completed, which means that the earliest completion time of a chore is the sum of the maximum of the earliest completion time of its preparations and the time required to complete the chore. This is a state transition equation:

Time [i] = max {time [j]} + len [i], there is an edge j → I

Such a state transition means that the transition to a certain point always requires that all its parent nodes have been traversed, which is also topological sorting

Start processing from the point with the penetration of 0 (the processed point is no longer counted into the penetration of its child nodes), and add the new point with the penetration of 0 found after each processing to the queue to be processed

(this code checks whether the parent node has been processed one by one, which is inferior to the above method)

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

vector<int> s[10010], f[10010];
int n, len[10010], ans[100010], deg[100010];

int main() {
    // freopen("in.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        ans[i] = 0x7FFFFFFF;
        int t;
        cin >> t >> len[i];
        while(cin >> t && t){
            s[t].push_back(i);
            f[i].push_back(t);
            deg[i]++;
        }
    }
    for(int i = 1; i <= n; i++) sort(s[i].begin(), s[i].end());

    ans[1] = len[1];
    for(int i = 1; i <= n; i++){
        for(auto j : s[i]){
            deg[j]--;
            if(!deg[j]){
                int big = -1;
                for(auto k : f[j]) big = max(big, ans[k]);
                ans[j] = len[j] + big;
            }
        }
    }

    int tmp = 0;
    for(int i = 1; i <= n; i++) tmp = max(tmp, ans[i]);
    printf("%d\n", tmp);

    return 0;
}

 3. Longest road

 

This is a directed acyclic graph (DAG)

Since both the starting point and the ending point are known, I directly wrote a bfs with 1 as the starting point, but this is a weighted graph. When I first reach a certain point, I can't guarantee that what I get at this time is the maximum distance to reach the point, but if not, it means that there are other paths to reach the point. It's not too late to update the answer here at that time, but the complexity becomes higher Yes, AC

I didn't know it was called SPFA until I finished writing it. Baidu found out a pile of disputes. Ignore those first

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int, int> P;        // After reading the following code, you will find that it is completely unnecessary to use it pair,Queue processing int That's it
queue<P> q;
vector<P> s[1510];
int n, m, dist[1510];

int main(){
    // freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    while(m--){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        s[u].push_back(make_pair(v, w));
    }
    q.push(make_pair(1, 0));

    while(!q.empty()){
        P cur = q.front();
        q.pop();

        for(auto i : s[cur.first])
            if(dist[i.first] < i.second + cur.second){
                dist[i.first] = i.second + cur.second;
                q.push(make_pair(i.first, dist[i.first]));    // I can see it here pair carry coals to newcastle
            }
    }

    printf("%d\n", dist[n] ? dist[n] : -1);

    return 0;
}