PAT 1175 Professional Ability Test-编程阁

这一题的大意PAT考试有一些等级考试在通过某些等级考试后才能去做另一些等级考试，可以把题目要求抽象成给出一个图，给出的这个图首先要判断它是不是有向无环图图，也就是题目中的
A plan is NOT consistent if there exists some test T so that T is a prerequisite of itself.
如果不是，题目上要求了不是的只能输出没有前提条件（入度为0）的等级考试：
You may take test x directly.，
其他一律输出error，（可能其他等级考试不在环中，但是它有前提条件（入度不为0）也输出error）。
如果是有向无环图，按题目要求先输出Okay.
如果是入度为0，输出：You may take test x directly.
如果入度不为0，我们来找所需分数最低，当分数一样时钱最多的路径。很明显dijkstra。
但题目上入度为0的点可能不止一个，而dijkstra是解决单源最短路的，我们可以再建一个超级源点，来把入度为0的点都被这个超级源点所指向，超级源点到这些入度为0的店的分数和钱都为0，这样我们就可以统一起来，只需要找从超级源点到各个点的最短路即可。
判断有无环，用拓扑排序的方式：

boolishuan(){queue<int>q;unordered_map<int,int>temp;temp=mp;for(inti=0;i<N;i++){if(temp[i]==0){q.push(i);}}intcnt=0;while(!q.empty()){intx=q.front();if(temp[x]==0){cnt++;}q.pop();for(inti=head[x];i!=-1;i=e[i].next){intu=e[i].to;temp[u]--;if(temp[u]==0){q.push(u);}}}if(cnt<N){returnfalse;}else{returntrue;}}

跑dijkstra算法，我习惯于用链式前向星存图+堆优化dijkstra。
但这一题需要注意的是，我们要在找分数最小的基础上，还要找钱最多的，如果通过保存每一条分数最小的最短路径，然后再用DFS来遍历枚举出钱最多的那一条边无疑是非常麻烦的，而且比超时，我们这里选择对堆的排序规则进行改造，使得它每次的最小值是分数最小的前提下，钱最多。

structstate{ints;intd;intu;//表示某一个点``};structcmp{booloperator()(conststate&a,conststate&b)const{if(a.s>b.s){returntrue;}elseif(a.s==b.s){if(a.d>b.d){returntrue;}else{returnfalse;}}else{returnfalse;}}};priority_queue<state,vector<state>,cmp>q;

这样就完美解决了。
我们只需要按照正常的方法跑dijkstra即可。
注意要用一个 int pre[1005]来保存前驱节点。
最后只需要逆序输出这些节点即可。
完整代码如下：

#include<bits/stdc++.h>#include<iostream>usingnamespacestd;//A是B的前置要求必须通过A不少于S才有资格去B//同时通过A不少于S将会接收到一个代金卷D元可以去B使用//同时PAT被设计人们可以有不同的计划，A计划不包含T因为T是它的前置要求//你的工作是去测试每一个计划并且辨别它是包含哪一个点//同时找到最简单的方式带有最小的S去得到一些测试的资格//如果最简单的方式不止一种找到一个可以赢得带进卷最多的intN;//测试的总共数量intM;//前置条件关系unordered_map<int,int>mp;structnode{intto;intnext;ints;intd;}e[1000005];structstate{ints;intd;intu;};structcmp{booloperator()(conststate&a,conststate&b)const{if(a.s>b.s){returntrue;}elseif(a.s==b.s){if(a.d>b.d){returntrue;}else{returnfalse;}}else{returnfalse;}}};intcut;inthead[1005];voidadd(intx,inty,ints,intd){e[cut].next=head[x];e[cut].to=y;e[cut].s=s;e[cut].d=d;head[x]=cut;cut++;}boolishuan(){queue<int>q;unordered_map<int,int>temp;temp=mp;for(inti=0;i<N;i++){if(temp[i]==0){q.push(i);}}intcnt=0;while(!q.empty()){intx=q.front();if(temp[x]==0){cnt++;}q.pop();for(inti=head[x];i!=-1;i=e[i].next){intu=e[i].to;temp[u]--;if(temp[u]==0){q.push(u);}}}if(cnt<N){returnfalse;}else{returntrue;}}intflag[1005];intdists[1005];priority_queue<state,vector<state>,cmp>q;intpre[1005];intdistd[1005];voiddijkstra(ints){memset(dists,0x3f,sizeof(dists));for(inti=0;i<1005;i++){distd[i]=-505;}memset(flag,0,sizeof(flag));dists[s]=0;distd[s]=0;q.push({dists[s],distd[s],s});while(!q.empty()){state z=q.top();q.pop();intu=z.u;if(flag[u]==0){flag[u]=1;for(inti=head[u];i!=-1;i=e[i].next){intv=e[i].to;intns=dists[u]+e[i].s;intnd=distd[u]+e[i].d;if(ns<dists[v]||(ns==dists[v]&&nd>distd[v])){dists[v]=ns;distd[v]=nd;pre[v]=u;q.push({ns,nd,v});}}}else{continue;}}}intmain(){cin>>N>>M;memset(head,-1,sizeof(head));for(inti=0;i<M;i++){intx;inty;ints;intd;cin>>x>>y>>s>>d;mp[y]++;add(x,y,s,d);}boolf=ishuan();if(f==1){cout<<"Okay."<<endl;//构造超级源点for(inti=0;i<N;i++){if(mp[i]==0){add(1004,i,0,0);}}//说明是入度为0的点dijkstra(1004);}else{cout<<"Impossible."<<endl;}intK;cin>>K;for(inti=0;i<K;i++){intx;cin>>x;if(mp[x]==0){cout<<"You may take test "<<x<<" directly."<<endl;}elseif(mp[x]!=0&&f==0){cout<<"Error."<<endl;}elseif(mp[x]!=0&&f==1){inttem=x;vector<int>ans;ans.push_back(tem);while(pre[tem]!=1004){ans.push_back(pre[tem]);tem=pre[tem];}for(inti=ans.size()-1;i>=0;i--){if(i!=ans.size()-1){cout<<"->"<<ans[i];}else{cout<<ans[i];}}cout<<endl;}//找符合条件的路径}return0;}