当前位置:首页 > 图论 > 正文
洛谷P1330封锁阳光大学
2110+

题目大意:一个图中有很多条路,在点上放河蟹,该点所有边都不能走,但相邻两点不能同时放河蟹,至少放多少个河蟹,才能使所有路都不能走?

题目描述

曹是一只爱刷街的老曹,暑假期间,他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹,感到不爽。河蟹决定封锁阳光大学,不让曹刷街。

阳光大学的校园是一张由N个点构成的无向图,N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁,当某个点被封锁后,与这个点相连的道路就被封锁了,曹就无法在与这些道路上刷街了。非常悲剧的一点是,河蟹是一种不和谐的生物,当两只河蟹封锁了相邻的两个点时,他们会发生冲突。

询问:最少需要多少只河蟹,可以封锁所有道路并且不发生冲突。

输入输出格式

输入格式:

第一行:两个整数N,M

接下来M行:每行两个整数A,B,表示点A到点B之间有道路相连。

输出格式:

仅一行:如果河蟹无法封锁所有道路,则输出“Impossible”,否则输出一个整数,表示最少需要多少只河蟹。

输入输出样例

输入样例#1:

【输入样例1】
3 3
1 2
1 3
2 3

【输入样例2】
3 2
1 2
2 3

输出样例#1:

【输出样例1】
Impossible

【输出样例2】
1

说明

【数据规模】

1<=N<=10000,1<=M<=100000,任意两点之间最多有一条道路。

解题思路

任意两点之间最多有一条道路是指什么呢?样例1中2到3有多少条路?????是指直接道路,没有重边?

首先,为什么样例1会Impossible?因为它存在奇数条边的环,这样是绝对会冲突的。怎么判断奇数环呢?在搜索过程中,记录各个点的深度,如果出现环的时候,两点的深度差是偶数,则是奇数环,此时设置ans为负无穷,最后根据他是否为负数即可判断是否需要输出Impossible。

接着,对于仅有偶数环的图,随便选一个点作为根结点,这个点要么放河蟹,要么不放:如果根结点放河蟹,结点深度奇偶性跟根结点相同的都要放河蟹,这是一种方案;另外一种方案是根结点不放河蟹,那么原来放河蟹的都不放,原来不放的都放。这两种方案选一个小的作为这个图放河蟹的最少河蟹数。

如果有多个连通块,累加起来即可。

程序实现

以下是树形动规实现方法,f[i]表示该点放河蟹,g[i]表示该点不放河蟹。如果i点放了河蟹,那么子结点全都不能放;如果i点没有放河蟹,那么子结点都要放河蟹(因为连接这两个点的边需要封锁)。

About

坚决不Copy代码!

本文标签:,,,,,,

洛谷P1330封锁阳光大学:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!