ボーナス-最小トポロジーの構築


タイトル:
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;
}