感觉难度不是很大,思路如下。
-
首先存储关系,即a的工资比b高,那么视为b指向a。
-
判断是否没有方案,即判断图中是否有环,用拓扑排序判断即可。
ps:不会有人不会吧 -
然后存储一个反环,判断一个点的工资,即为基础100元+该点在图中可到达最远点的距离 个人的方法是递归,去找第一步能到达点的在图中可到达最远点的距离,以此类推。
AC code
本蒟蒻第一篇题解,有些奇奇怪怪的东西不负责
#include<bits/stdc++.h>
using name space std;
int n,m;
long long cnt=0;
vector <int> g[10001],rg[10001];
queue <int> q;
int inq[10001];
int maxs(int x){
int maxl=-1;
if(rg[x].size()==0) return 0;
for(int v:rg[x]){
maxl=max(maxs(v),maxl);//调了一下午没套max
}
return maxl;
}
int mian{
cin>>n>>m;
cnt+=100*n;
int a,b;
for(int i=1;i<=m;i++){
cin>>a>>b;
g[b].push_back(a);//存环
rg[a].push_back(b);//存反还
inq[a]++;//入度数组
}
for(int i=1;i<=n;i++){
if(inq[i]==0) q.push(i);
}
int k=n;
while(!q.empty()){//拓扑
int u=q.front();
q.pop();
n--;
for(int i=0;i<g[u].size();i++){
int f=g[u][i];
inq[f]--;
if(!inq[f]) q.push(f);
}
}
if(n>0){
cout<<"Poor Xed";
}else{
for(int i=1;i<=k;i++){
cnt+=maxs(i);
}
cout<<cnt;
}
return 0;
}