#BZOJ4938. router

router

题目描述

你现在要造一个路由器,路由器可以看成一个有向图,他包含n个输入节点,编号1~n,n个输出节点,编号n+1~2n
,k个内部节点,标号2n+1~2n+k,还有m条有向边。节点x可以向节点y发送信息的条件是:x=y或者x可以向z发送信
息,并且存在一条从z到y的边。路由器能正常工作的条件是:每个输入节点都能向每个输出节点发送信息对于任意
一个输入节点,能向他发送信息的只有他自己对于任意一个输出节点,他只能向他自己发送信息如果x不等于y并且
x能向y发送信息,那么y不能向x发送信息如果x不等于y并且x能向y发送信息,那么x到y的路径是唯一的不能有重边
一个节点的耗电量是能向他发送信息的输入节点个数乘以他能发送信息到达的输出节点个数给定n,对边的数量的
限制mlim,和对耗电量最大的节点的耗电量的限制,并要求总节点数<=500000请你构造一个路由器
提交答案题,无法测评