PAT (Level A) Fall 2020 Exam 7-4 Professional Ability Test

7-4 Professional Ability Test (30 points)

Professional Ability Test (PAT) consists of several series of subject tests. Each test is divided into several levels. Level A is a prerequisite of Level B if one must pass Level A with a score no less than S in order to be qualified to take Level B. At the mean time, one who passes Level A with a score no less than S will receive a voucher of D yuans (Chinese dollar) for taking Level B.

At the moment, this PAT is only in design and hence people would make up different plans. A plan is NOT consistent if there exists some test T so that T is a prerequisite of itself. Your job is to test each plan and tell if it is a consistent one, and at the mean time, find the easiest way (with minimum total S) to obtain the certificate of any subject test. If the easiest way is not unique, find the one that one can win the maximum total value of vouchers.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤1000) and M, being the total numbers of tests and prerequisite relations, respectively. Then M lines follow, each describes a prerequisite relation in the following format:

T1 T2 S D

where T1 and T2 are the indices (from 0 to N−1) of the two distinct tests; S is the minimum score (in the range (0, 100]) required to pass T1 in order to be qualified to take T2; and D is the value of the voucher (in the range (0, 500]) one can receive if one passes T1 with a score no less than S and plan to take T2. It is guaranteed that at most one pair of S and D are defined for a prerequisite relation.

Then another positive integer K (≤N) is given, followed by K queries of tests. All the numbers in a line are separated by spaces.

Output Specification:

Print in the first line Okay. if the whole plan is consistent, or Impossible. if not.

If the plan is consistent, for each query of test T, print in a line the easiest way to obtain the certificate of this test, in the format:

T0->T1->...->T

However, if T is the first level of some subject test (with no prerequisite), print You may take test T directly. instead.

If the plan is impossible, for each query of test T, check if one can take it directly or not. If the answer is yes, print in a line You may take test T directly.; or print Error. instead.

Sample Input 1:

8 15
0 1 50 50
1 2 20 20
3 4 90 90
3 7 90 80
4 5 20 20
7 5 10 10
5 6 10 10
0 4 80 60
3 1 50 45
1 4 30 20
1 5 50 20
2 4 10 10
7 2 10 30
2 5 30 20
2 6 40 60
8
0 1 2 3 4 5 6 7

Sample Output 1:

Okay.
You may take test 0 directly.
0->1
0->1->2
You may take test 3 directly.
0->1->2->4
0->1->2->4->5
0->1->2->6
3->7

Sample Input 2:

4 5
0 1 1 10
1 2 2 10
3 0 4 10
3 2 5 10
2 0 3 10
2
3 1

Sample Output 2:

Impossible.
You may take test 3 directly.
Error.

Subject restrictions:

Topic meaning:

There are N exams, and M exams are related to each other. Now we call the N exams and the M relations an exam plan. May I ask if the current plan is a consistent plan, and gives the K exams? The query of the exam, if it is a consistent plan, requires the fastest way to pass the current exam, if there are multiple, choose the one that gets the most vouchers. If it is not a consistent plan, then judge whether the current test T can be taken directly. If so, output You may take test T directly. Otherwise, output Error.

Algorithm idea:

First of all, we must understand the meaning of the question. plan refers to each test case, not each query. The method of consistent judgment is to judge whether there is a cycle in the current graph. Since it is a directed graph, topological sorting can be used to judge.
For graphs with rings, it is necessary to know whether the in-degree of the node currently queried is 0, so use the zeroDegree set to save each node whose in-degree is 0 (the inDegree will change during topological sorting), for the in-degree of 0 The point directly outputs You may take test T directly. It's fine, otherwise it outputs Error.
For graphs without rings, we need to find a shortest path to the query node, which is solved by Dijkstra's algorithm, but there is no given starting point. Read the question carefully and find that the starting point must be those nodes that are read as 0 , because only points with an in-degree of 0 can be tested without any preconditions, but if the shortest path is obtained by traversing each starting point with an in-degree of 0, the last two test points will run out of time, so here we use a small The trick is to set up a vertex whose in-degree is 0, and point the vertex to all vertices with in-degree 0 in the current graph, and set the edge weight to 0, so that the vertices with in-degree 0 in the whole graph are exactly There is only one, and the acquisition of the shortest path of each vertex only needs to perform Dijkstra's algorithm once.

Here is a brief description of why this method is feasible, because starting from this point, it must first pass through the starting point with an in-degree of 0 in the original graph, that is, the real starting point, then the shortest path of all nodes in the graph must be compared with all original graphs. It is obtained after the starting point in the graph, and the edge weight is 0, which does not affect the shortest distance.

Then for each queried candidate subject, determine whether it is a node with an in-degree of 0 in the original image, if so, output You may take test T directly. At the time, the predecessor of each node is stored in the pre array, so it can be obtained directly)

be careful:

  • 1. If Dijkstra's algorithm is used multiple times, the last two test points will time out.

Submit the result:

AC code:

#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<unordered_set>

using namespace std;

int N,M;//Vertices and Edges
vector<int> Adj[1005];//adjacency list
int score[1005][1005];//score[a][b] represents the lowest score obtained by test point a to qualify for test b
int voucher[1005][1005];//voucher[a][b] means that a test point can get score[a][b] and above to get a voucher for test b
int inDegree[1005];// in-degree of each vertex
bool inQueue[1005];// Mark a node that has been enqueued
unordered_set<int> zeroDegree;// All vertices with in-degree 0 in the graph, here refers to the vertices with in-degree 0 in the original graph 

// Topological sort to determine whether a cycle exists 
bool topologicalOrder(){
    queue<int> q;
    int num = 0;
    // Enqueue all vertices with in-degree 0
    for(int i=0;i<N;++i){
        if(inDegree[i]==0){
            inQueue[i] = true;
            q.push(i);
        }
    }
    while (!q.empty()){
        int t = q.front();
        q.pop();
        ++num;//Count the number of nodes in the queue 
        // Decrease all the in-degrees of the critical points of t by one
        for(int vertex:Adj[t]){
            --inDegree[vertex];
            // Enqueue a node with an in-degree of 0 and no enqueue
            if(inDegree[vertex]==0){
                q.push(vertex);
            }
        }
    }
    return num==N;// true means no ring 
}

int dis[1005];// The shortest distance from each node to the starting point (score)
int money[1005];// Get the maximum voucher from each node to the starting point
bool visited[1005];// Mark whether each node is visited
int pre[1005];// The predecessor node of each node

void Dijsktra(int start){
    fill(dis,dis+1005,0x3ffffff);
    dis[start] = 0;
    money[start] = 0;
    for(int i=0;i<N+1;++i){// N+1 vertices 
        // Find the unvisited node with the shortest distance from the starting point
        int min_dis = 0x3fffff;
        int min_index = -1;
        for(int j=0;j<N+1;++j){
            if(!visited[j]&&dis[j]<min_dis){
                min_dis = dis[j];
                min_index = j;
            }
        }
        if(min_index==-1) return;
        visited[min_index] = true;
        // optimized path
        for(int j=0;j<Adj[min_index].size();++j){
            int v = Adj[min_index][j];
            if(!visited[v]){
                if(dis[v]>dis[min_index]+score[min_index][v]){
                    // The current path is shorter
                    pre[v] = min_index;
                    dis[v] = dis[min_index]+score[min_index][v];
                    money[v] = money[min_index] + voucher[min_index][v];
                } else if(dis[v]==dis[min_index]+score[min_index][v]&&money[v]<money[min_index]+voucher[min_index][v]){
                    // Requires the same test scores, but earns more vouchers
                    pre[v] = min_index;
                    money[v] = money[min_index] + voucher[min_index][v];
                }
            }
        }
    }
}

void DFS(int end){
    if(pre[end]==N){
        // reach the starting point 
        printf("%d",end);
        return;
    }
    DFS(pre[end]);
    printf("->%d",end);
}

void consistent(int query[],int K){
    Dijsktra(N);// Get the shortest distance and path for each node 
    for(int i=0;i<K;++i){
        if(zeroDegree.find(query[i])!=zeroDegree.end()){
            // There are no prerequisites for the current exam
            printf("You may take test %d directly.",query[i]);
        }else{
            DFS(query[i]);
        }
        if(i<K-1) printf("\n");
    }
}

void notConsistent(int query[],int K){
    for(int i=0;i<K;++i){
        if(zeroDegree.find(query[i])!=zeroDegree.end()){
            // There are no prerequisites for the current exam
            printf("You may take test %d directly.",query[i]);
        }else{
            printf("Error.");
        }
        if(i<K-1) printf("\n");
    }
}

int main(){
    scanf("%d %d",&N,&M);
    for (int i = 0; i < M; ++i) {
        int a,b;
        scanf("%d %d",&a,&b);
        scanf("%d %d",&score[a][b],&voucher[a][b]);
        ++inDegree[b];
        Adj[a].push_back(b);
    }
    // Add a vertex with in-degree 0, vertex number N, and connect an edge with all vertices with in-degree 0, so that N is the only vertex with in-degree 0 
    for(int i=0;i<N;++i){
        if(inDegree[i]==0){
            Adj[N].push_back(i);
            zeroDegree.insert(i);
        }
    }
    int K;
    scanf("%d",&K);
    int query[K];
    for(int i=0;i<K;++i){
        scanf("%d",&query[i]);
    }
    bool isOk = topologicalOrder();
    if(isOk){
        printf("Okay.\n");
        consistent(query,K); 
    } else {
        printf("Impossible.\n");
        notConsistent(query,K); 
    }
    return 0;
}

Tags: C++ Algorithm

Posted by CodeEye on Wed, 04 May 2022 05:57:26 +0300