ボーナス-最小トポロジーの構築
タイトル:
Mr.Zさんは気持ちがいいので、社員一人一人にボーナスを出すことにしました.会社は一人一人の本年の会社での貢献を基準にボーナスのいくらを計算することにした.そこでMr.Zはm者協議の開催を命じた.会談に参加した各代表は「従業員aのボーナスはbより高いと思います」と自分の意見を出した.Mr.Zは、代表の意見を満たすボーナス案を見つけ、総ボーナス数を最小限に抑えることにした.従業員1人当たりのボーナスは最低100元です.
最初の行の2つの整数n,mを入力して、従業員の総数と代表数を表します.以下のm行、各行2個の整数a,bは、ある代表がa番目の従業員のボーナスがb番目の従業員より高いべきだと考えていることを示す.n<=10000,m<=20000
出力が合法的な方案を探し当てることができないならば、“Poor Xed”を出力します;そうでなければ、最低総ボーナスを出力します.
サンプル入力2 1 1 2出力201
構想:トポロジーボードのサブ問題は、aがbより高い場合はaにbにエッジを接続させ、入力が終わったら直接トポロジーにし、最後に検索したトポロジーシーケンスを加算すればよい.
トポロジーの基礎がない場合は、このブログに移動してください.
コードは次のとおりです.
Mr.Zさんは気持ちがいいので、社員一人一人にボーナスを出すことにしました.会社は一人一人の本年の会社での貢献を基準にボーナスのいくらを計算することにした.そこでMr.Zはm者協議の開催を命じた.会談に参加した各代表は「従業員aのボーナスはbより高いと思います」と自分の意見を出した.Mr.Zは、代表の意見を満たすボーナス案を見つけ、総ボーナス数を最小限に抑えることにした.従業員1人当たりのボーナスは最低100元です.
最初の行の2つの整数n,mを入力して、従業員の総数と代表数を表します.以下のm行、各行2個の整数a,bは、ある代表がa番目の従業員のボーナスがb番目の従業員より高いべきだと考えていることを示す.n<=10000,m<=20000
出力が合法的な方案を探し当てることができないならば、“Poor Xed”を出力します;そうでなければ、最低総ボーナスを出力します.
サンプル入力2 1 1 2出力201
構想:トポロジーボードのサブ問題は、aがbより高い場合はaにbにエッジを接続させ、入力が終わったら直接トポロジーにし、最後に検索したトポロジーシーケンスを加算すればよい.
トポロジーの基礎がない場合は、このブログに移動してください.
コードは次のとおりです.
#include
using namespace std;
int n,m,du[100001],a[1000010],cnt,ans;
vector<int >v[100010];
void topo(){
queue<int >q;
for(int i=1;i<=n;i++){
if(du[i]==0){
q.push(i);
}
}// 0
// int num=0;
while(!q.empty()){
int u=q.front();
q.pop();
cnt++;
for(int i=0;i<v[u].size();i++){
if(--du[v[u][i]]==0){// -1, 0
q.push(v[u][i]);
}
a[v[u][i]]=max(a[v[u][i]],a[u]+1);// , , 。
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
v[b].push_back(a);//
du[a]++;// ++
}
for(int i=1;i<=n;i++){
a[i]=100;// 100, 100 。
}
topo();
if(cnt!=n){
cout<<"Poor Xed";
return 0;
}// n
for(int i=1;i<=n;i++){
ans+=a[i];
}
cout<<ans;
return 0;
}