codeforces 22 C. System Administrator

http://codeforces.com/contest/22/problem/C
题意:要求用n个点m条边构造一个不允许有重边的图,满足当去掉点v的时候,剩下的n-1个不联通。如果有答案输出任意,没答案输出-1.
思路:首先如果n个点要联通。。至少有n-1条边,此时为一棵树。但是是不是边越多越好呢?显然是不可以的。满足去掉一个点使得n-1个点不联通的情况为,存在一个点u只和v相连,不和任意任何其他点相连,那么当去掉v点,u点就变成不可到达了。边数最多的情况就是,除了v点以外的n-1个点,每个点的度都是n-2(去掉自身以及u点还有n-2个点),,那么除去u点以外的n-1个点的度数就是(n-1)*(n-2),边数则为(n-1)*(n-2)/2,再加一条连接u的边,所以图的最大边数为(n-1)*(n-2)/2+1,最小为n-1.

如果有解,那么接下来的问题是构造。

我是按照如下方式构造的:

先构造一条链,将u点放在第一个,v点放在第二个。不妨当v=1时令u=2,否则u=1;

m-=n-1,如果m还有剩余,那么从第二个点开始,一直到第n-2个点,每个点与至少隔1个点的其他点相连,直到边数没有剩余。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz