校赛的一道题目 难度不大 不过还是挺有趣的
题意：给定一个有向图，问此图是不是一个DAG且不包含重边 如果是的话 回答最多可以添加多少条边且图仍然是个DAG
考虑对于任意一个点u 添加一条边（u,v）且添加后图仍然是DAG 那么添加之前 从点v一定不可以访问到点u
显然 可以用拓扑排序解决
代码没拷贝下来 写一个简单的伪代码吧
初始ans=0
每次选取一个入度为0的点 此时图中剩余的点还有n个 ans+=n-当前点的出度
删除当前点
循环直到图中的点全部删完
cout<<ans
嗯 算是拓扑排序一个比较有趣的应用。
出题人写的解题报告http://www.acmm.club/posts/sysucpc2017_solutions/