wcwswswws的日记

wcwswswws

sgu371+sgu381

sgu371
题意:the city of S***的地铁有两种路线:一种是环线,环线由若干个环(节点数在3~10之间),所有的环构成一条链,每个环仅与其相邻的环有一个公共节点,且每个节点最多只能在2个环上,如此串成链;另一种是支线,每个环上的不是两环连接处的节点最多可以延伸一条支线。现在给出节点数N和边数M,求地铁建设方案。

水题。多一环可多一边。先建环,后加点,最后加支线。

sgu381
题意:给一个图,每条边e连接的两点u,v都有权值w(e,u)和w(e,v)。权值只有1和-1两种。有向图指的是每条边e上的权值积为-1。有一种操作是对于某个点v,对于所有e,若存在w(e,v),则w(e,v)*=-1。求最少的操作使图变为有向。

水题。当一个连通块上任意点确定是否执行操作后,整个连通块每个点是否执行操作就确定了。

posted on 2012-02-20 13:02 世界厕所所长 阅读(221) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理