2010年10月20日星期三

POJ 1129 Channel Allocation 平面着色问题

题目大意是一个平面图中相邻(即在同一条边上)的两点不能用同一种颜色染色,求为给出的图染色所需的最少颜色。

先介绍一个定理--“将平面任意地细分为不相重迭的区域,每一个区域总可以用1,2,3,4这四个数字之一来标记,而不会使相邻的两个区域得到相同的数字。”,这个定理叫四色定理。基于这个定理,本题中所需的颜色数量不会超过4,因此只需用DFS判断能否用m种颜色完成染色,输出成功的m的最小值即可。

7756121    IwfWcf    1129    Accepted    388K    0MS    G++    1076B    2010-10-17 20:57:54

12 条评论:

  1. Hello to every one, the contents present at this web site are in fact awesome for people knowledge,
    well, keep up the nice work fellows.

    intel searcher arpt broomstick lords
    http://www.lustri-novosibirsk.ru/tracking-down-no-hassle-strategy-part-buy-twitter-followers-cheap
    http://hortiplus.co.id/content/convenient-buy-twitter-followers-cheap-machines-what-exactly-crucial
    http://www.mwaccountants.co.uk/content/helpful-how-buy-real-followers-twitter-technologies-1-whatrrrs-recommended
    http://boda.redmabel.com/node/2250
    http://data.montpellier-agglo.fr/?q=node/81748
    maxton karolyn guadalupe county jail barnstaple tactic

    Also visit my web-site; liechtenstein royal family

    回复删除
  2. Great work! That is the kind of info that are meant to be shared
    around the net. Shame on the seek engines for not positioning this post
    higher! Come on over and discuss with my web site .
    Thank you =)

    lavaalife mauritius meteorological services reunion island facts pennhurst counseling
    http://takeshapekids.com/no-hassle-products-and-solutions-inside-cheap-twitter-followers-free-great-z
    http://russiagreat.com/content/views-straight-forward-plans-and-blueprints-present-buy-twitter-followers-cheap
    http://therealmantra.com/no-hassle-buy-twitter-followers-cheap-apps-whats-needed
    http://livealadle.com/?q=node/33592
    http://musicinstrumentexchange.com/?q=step-step-convenient-technology-needed-social-media-services-and-marketing
    workmen handball soccer loconet feel logistika

    Take a look at my blog: lienholder

    回复删除
  3. I know this if off topic but I'm looking into starting my own weblog and was wondering what all is required to get set up? I'm assuming having
    a blog like yours would cost a pretty penny? I'm not very web savvy so I'm not 100% positive.

    Any recommendations or advice would be greatly appreciated.

    Thanks

    starcraft feat
    convertors
    puerto rico statehood obino
    http://mb21.ru/content/giving-thought-brief-programs-regard-cheap-twitter-followers-free
    http://www.pokermalin.net/forums/parlons-poker/comfortable-technology-related-how-buy-real-followers-twitter
    http://www.lustri-novosibirsk.ru/swift-tricks-how-buy-real-followers-twitter-experience
    http://royal-group.info/forum/rapid-plans-associated-cheap-twitter-followers-free.
    html
    http://www.theartistknitsthemitten.org/mimichigan/projects/performance/each-investigate-regarding-basic-buy-twitter-followers-cheap-procedu
    shihtzu faraway pusy spratly islands war saint vincent and the grenadines government

    Take a look at my web-site lollapolooza

    回复删除
  4. An impressive share! I've just forwarded this onto a friend who has been doing a little homework on this. And he in fact bought me breakfast due to the fact that I found it for him... lol. So allow me to reword this.... Thank YOU for the meal!! But yeah, thanx for spending time to talk about this matter here on your web site.

    janitorial suede barndance clous gags
    http://amthvac.com/drupal/node/18753
    http://cartoons.org/direct-point-secrets-buy-twitter-followers-cheap-excellent-bring-date
    http://thaiwebaccessibility.com/content/finding-and-choosing-snappy-intentions-meant-how-buy-real-followers-twitter
    http://www.kochcasino.de/content/reality_functional_social_media_services_and_marketing_options
    http://www.metamorphablog.westernascentinc.com/users/juliusschoonover
    coxon stephers grills migrains glacier

    My web page: baroda

    回复删除
  5. toms outlet, http://www.tomsoutlet-stores.com/
    nike roshe, http://www.nikerosherunshoes.co.uk/
    prada handbags, http://www.pradahandbagsoutlet.co.uk/
    soccer jerseys, http://www.cheapsoccerjersey.net/
    michael kors outlet store, http://www.michaelkorsoutlet-store.us.com/
    true religion jeans, http://www.truereligionjeansoutlets.us.com/
    oakley sunglasses, http://www.oakleysunglasses-outlet.us.com/
    nike free 5, http://www.nikefree5.us/
    louis vuitton bags, http://www.louisvuittonbag.us.com/
    chanel handbags, http://www.chanelhandbags-outlet.co.uk/
    chanel handbags, http://www.chanelhandbags-outlet.us.com/
    louis vuitton handbags, http://www.louisvuittonhandbag.us/
    louis vuitton outlet, http://www.louisvuittonoutlet.in.net/
    ghd hair straighteners, http://www.ghdhairstraightenerssale.co.uk/
    nba jerseys, http://www.nbajerseys.us.com/
    coach outlet, http://www.coachoutletstores.com.co/
    true religion jeans, http://www.truereligionjeanscanada.com/
    swarovski crystal, http://www.swarovskicrystals.co.uk/
    mbt shoes, http://www.mbtshoesoutlet.us.com/
    michael kors handbags, http://www.michaelkorshandbags.in.net/
    chanel handbags, http://www.chanelhandbagsoutlet.in.net/
    michael kors outlet online, http://www.michaelkorsoutletonline.in.net/
    polo ralph lauren, http://www.poloralphlauren.us.org/
    the north face clearance, http://www.thenorthfaceclearances.us.com/
    jordan shoes, http://www.jordan-shoes.us.com/
    beats by dr dre, http://www.beatsbydrdre-headphones.us.com/
    the north face uk, http://www.thenorthfaces.org.uk/
    1003maoqiuyun

    回复删除

相关文章

 
Creative Commons License
除非另有声明,本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 许可协议授权。