基于图论的奖金分配问题.docVIP

五、详细设计 #include iostream #include vector using namespace std; //图结点 typedef struct Node { int to; Node* next; Node(int to_ = 0, Node* next_ = NULL) { to = to_; next = next_; } }Node; //判断图是否有环 bool isCircle(const vectorNode edges) { int i; //记录各个结点的入度 vectorint indegree(edges.size(), 0); for (i = 1; i edges.size(); ++i) { Node* node = edges[i].next; while (node) { indegree[node-to] ++; node = node-next; } } //记录入度为0的结点 vectorint indegree0; for (i = 1; i edges.size(); ++i) { if (indegree[i] == 0) { indegree0.push_back(i); } } //利用队列实现是否存在环的判断 for (i = 0; i indegree0.size(); ++i) { Node *node = edges[indegree0[i]].next; while (node) { indegree[node-to] --; if (indegree[node-to] == 0) { indegree0.push_back(node-to); } node = node-next; } } return indegree0.size() edges.size() - 1; } //利用bfs计算各个员工的奖金 int solve(const vectorNode edges) { int i; //记录各个结点的入度 vectorint indegree(edges.size(), 0); for (i = 1; i edges.size(); ++i) { Node* node = edges[i].next; while (node) { indegree[node-to] ++; node = node-next; } } //记录入度为0的结点 vectorint tmp; for (i = 1; i edges.size(); ++i) { if (indegree[i] == 0) { tmp.push_back(i); } } vectorbool isVisited(edges.size(), false); vectorint bnous(edges.size(), 100); //利用队列实现bfs，利用bfs计算各个员工的奖金 for (i = 0; i tmp.size(); ++i ) { Node* node = edges[tmp[i]].next; while (node) { if (bnous[node-to] bnous[tmp[i]] + 1) { bnous[node-to] = bnous[tmp[i]] + 1; } tmp.push_back(node-to); node = node-next; } } int ret = 0; //输出奖金 for (i = 1; i bnous.size(); ++i) { ret += bnous[i]; } return ret; } //主函数 int main() { vectorNode edges; int n, m; cinnm; edges.resize(n + 1); //输入边 while (m--) { int from, to; cintofrom; //构造图 Node *newNode = new Node(to, edges[from].next); edges[from].next = newNode; } //判断是否存在环 if (isCircle(edges)) { coutPoor Xedendl; } else { coutsolve(edges