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 世界厕所所长 阅读(232) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


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