PIPI OJ 1203: PIPI发工资（拓扑排序）

本文主要是介绍PIPI OJ 1203: PIPI发工资（拓扑排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1203: PIPI发工资

菜鸟生成记(75)

主思路：题中提到了,a,b为上下级关系,a的工资要高于b,结合样例

2 2
1 2
2 1
-1

这一题需要拓扑排序;同时要反向建建(正向错误75%,最下面解释,正向建边的错误之处)

#include<bits/stdc++.h>
using namespace std;
const int N=2e4;
int n,m;
vector<int>e[N];
int in1[N];
queue<pair<int,int> >q;
void clear_()
{memset(in1,0,sizeof in1);//入度标记清空 for(int i=1;i<=n;i++)//邻接表清空 e[i].clear();while(q.size())//队列清空 q.pop();
}
int dagsort()//拓扑排序 
{int ans=0;int num=0;for(int i=1;i<=n;i++)if(!in1[i])//入度为0的全部放入队列 q.push(make_pair(i,0));//默认步数为0 while(q.size())//拓扑排序 {pair<int,int> t=q.front();q.pop();int x=t.first;int step=t.second;num++;//经过点的个数 for(int i=0;i<e[x].size();i++){int v=e[x][i];in1[v]--;if(!in1[v]){//当前步数等于上一层步数加一 ans+=step+1;//步数累加 q.push(make_pair(v,step+1));}}}//加上n个人的基础工资 ans+=888*n;if(num==n)//拓扑排序经过所以点,说明无环 return ans;else//否者有环 return -1;
}
/*
6 5
1 2
2 3
3 6
3 5
4 3
*/ 
int main()
{while(cin>>n>>m){clear_();for(int i=1;i<=m;i++){int u,v;cin>>u>>v;e[v].push_back(u);//反向建边//(正向建边会使一些点等级降低,进而使步数增加)//有多个结点到达A点,//这种情况正向建边会使A点的等级降低 in1[u]++;//入度 }cout<<dagsort()<<endl;}return 0;
}