# PAT（甲级）2020年秋季考试 7-4 Professional Ability Test

2020-12-06 20:01:44 乔梓鑫

## 7-4 Professional Ability Test (30分)

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.``````

#### 注意点：

• 1、如果多次使用迪杰斯特拉算法，最后两个测试点会超时。

#### AC代码：

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

using namespace std;

int N,M;//顶点数和边数
int score[1005][1005];//score[a][b]代表a测试点获得的最低得分可以有资格考b考试
int voucher[1005][1005];//voucher[a][b]代表a测试点获得score[a][b]及以上分数可以得到考b的代金券
int inDegree[1005];// 每一个顶点的入度
bool inQueue[1005];// 标记已经入队的节点
unordered_set<int> zeroDegree;// 图中所有入度为0的顶点,这里指原图中入度为0的顶点

// 拓扑排序判断是否有环存在
bool topologicalOrder(){
queue<int> q;
int num = 0;
// 入队所有入度为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;//统计入队的结点个数
// 将t的临界点的入度全部减一
--inDegree[vertex];
// 将入度为0且没有入队的节点入队
if(inDegree[vertex]==0){
q.push(vertex);
}
}
}
return num==N;// true表示没有环
}

int dis[1005];// 每一个节点到起点的最短距离(分数)
int money[1005];// 每一个节点到起点获得到最大代金券
bool visited[1005];// 标记每一个节点是否访问
int pre[1005];// 每一个节点的前驱节点

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个顶点
// 找出距离起点最短的未访问节点
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;
// 优化路径
if(!visited[v]){
if(dis[v]>dis[min_index]+score[min_index][v]){
// 当前路径更短
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]){
// 需要考试的分数一样，但是获得的代金券更多
pre[v] = min_index;
money[v] = money[min_index] + voucher[min_index][v];
}
}
}
}
}

void DFS(int end){
if(pre[end]==N){
// 到达起点
printf("%d",end);
return;
}
DFS(pre[end]);
printf("->%d",end);
}

void consistent(int query[],int K){
Dijsktra(N);// 获得每一个结点的最短距离和路径
for(int i=0;i<K;++i){
if(zeroDegree.find(query[i])!=zeroDegree.end()){
// 当前考试没有前置条件
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()){
// 当前考试没有前置条件
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];
}
// 添加一个入度为0的顶点,顶点编号为N,与所有入度为0的顶点连接一条边，这样N就是唯一的入度为0的顶点了
for(int i=0;i<N;++i){
if(inDegree[i]==0){
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;
}``````

https://segmentfault.com/a/1190000038393142