Keengle's Blog

最近好忙，所以都没时间打理博客了，并且ghs的最后一个ip都壮烈牺牲，搞得没心情啊。

不管怎样，还是发发牢骚吧。

广州的交通实在是不敢恭维，本来就不堪一击的交通状况，正在搞一个叫什么BRT的工程，在公路中间弄一条人行道出来，很是奇怪。记得有一天星期一，天气下雨了，广州交通直接瘫痪，等公交车的人站得到处都是，其实我怀疑这交通瘫痪的原因是天气呢，还是在公交车站等公交的人们呢，或者二者都有吧。我也在挤公交的行列，上了很挤的公交车，大家都在挤，更严重的是每人还有一把湿得正在滴水的伞，场面非常壮观。

坐公交车多了，就会想到些题目，现在出个关于公交车站的题目，有兴趣的读者可以想一下，我也只是想到题目，还没有做出来的。如果读者做出来了，欢迎秀一秀你的方案，估算一下时间复杂度什么的，呵呵。

***********************以下是题目

经过某个公交车站A的班车有L条线，不妨设此车站A都是这些路线的源点，另外还有S个公交站点，L条线分别经过某些站点并在预设好的站点停下，每条路线不会循环。现在A站的公交车太多了，要把A站的分成几个小站，就像岗顶1站，岗顶2站这样，假设现在要将A站分为n个站，其它的S个公交站点不分小站。

但为了乘客方便，要尽量使去某个站的乘客只在一个站里等车。例如，某个乘客现在在A站，他要前往B站，但A站在分为A1,A2,A3，其中A1有2条线程到达B，A2有5条线程到达B，A3有4条线程到达B，这样乘客应该就在A2站等车，其它的2+4条线的站就称为对于B站无用的线路。

现在要求你算出一个case中如何安排A站的公交车在n个小站中分布，能够使无用线路最小，输出这个最小值。无用线路指对于另外的S个公交站点的每一个站的无用线路数的求和。

输入：一行有3个数，L表示公交线路，S表示公交站点，n表示把A站分为的小站数目。接下有L行，每一行表示一条公交经过的站点,这些公交车都是从A站出发的，站点用1,2,...,S表示。

L S n

L行，每一行是公交路线

例如：

5 10 3

1 6 7 2 9

3 5 1 8 6 10 7

1 2 5 4 7 6

5 1 3 6 4

9 7 8 10

输出：如何安排A站的公交车在n个小站中分布，能够使无用线路最小，输出这个最小值。

(题目来源:Keengle's Blog www.kgblog.net或者keeng2008.appspot.com )