ACM¾ºÈü×÷Ϊ´óѧÉú±à³ÌÁìÓò¹ú¼Ê×îÖØÒª¶¥¼¶µÄ±ÈÈü£¬Æäº¬½ðÁ¿£¬²»ÊÇÀàËÆÓÚÊýѧ½¨Ä£Óë½ÌѧÈí¼þ£¨µ±È»ÃÎÏè¶ùûÓбáµÍÕâЩ±ÈÈüµÄÒâ˼£¬Ö»ÒªÊDZÈÈü×÷ΪѧÉú¾ÍÒ»¶¨ÓÐÊÕ»ñ£¬Ö»²»¹ýÕæÕýº¬½ðÁ¿µÄÎÊÌâ¡££©Ö®ÀàÄܹ»±ÈÄâµÄ¡£ÏÂÃæ²©ÎĵÄ×÷ÕßµÄÌå»á£¬Í¦ºÃ£¬ÊÕÔÚÕâÀï£¬ÍÆ¼öÀ´ÕâÀïµÄͬ־ÃǶÁÒ»¶Á£¬»òÕß˼¿¼Ò»Ï£¬ÎÒÃǾ¿¾¹ÔÚ×öʲô²Å¶Ô×ÔÒѵij¤Ô¶·¢Õ¹ÓÐÒæ£¿
£½£½£½£½£½£½£½£½£½£½£½£½
×÷Ϊһ¸ö¸ãÁ˶àÄêACMµ«Ã»ÓÐʲô³É¼¨£¬Ä¿Ç°¸Õ¸ÕÈëÖ°¼¸¸öÔµIJËÄñ£¬ÎÒÀ´Ëæ±ãºú˵¼¸µã¡£Ð´µ½×îºó·¢ÏÖÓеĵط½ÉÔ΢ƫ¼¤Á˵㣬²»¹ýÀÁµÃ¸ÄÁË£¬»¶ÓÂ¥ÏÂÀ´ÅÄ¡£
1. ACM¾ºÈü²»ÊǸãÑо¿£¬µ«ÊǸã¹ýACMµÄѧÉú£¬ÖÁÉÙ²»±È²»¸ãACMµÄѧÉú¸üÔ¶Àë¿ÆÑ§Ñо¿£¬ÎÒÉõÖÁ¸Ò´óµ¨µØ½²£¬´Óͳ¼ÆÒâÒåÉϽ²ACMer»á¸üϲ»¶¸ãÑо¿¡£Êµ¼ÊÉÏ£¬¾ÍÎÒ¶ÔÉí±ßºÍÍøÉÏÌÖÂÛȺµÄ¹Û²ì£¬¶Ô¼ÆËã»ú¿ÆÑ§Ê¼ÖÕ±£³ÖÑÏËàÈÏÕæÌ¬¶ÈµÄ¸ü¶àµØÊÇACMer¡£ÔÚACMerµÄÌÖÂÛÀï¾³£¶¯²»¶¯¾Í³öÏÖÐÎʽÓïÑÔ¡¢¿É¼ÆËãÐÔ¡¢±àÒëÔÀíÒÔ¼°×îÓÅ»¯¡¢¸ÅÂÊ¡¢Í³¼ÆµÈµÈÄÚÈÝ£¬¶ø´ó²¿·Öͨ³£µÄ¼ÆËã»úרҵѧÉúÍùÍùÒ²Ö»°Ñ¼ÆËã»ú¿ÆÑ§¼òµ¥µØµÈͬÓÚ±à³Ì¶øÒÑ¡£ÎÒ±¾È˾ÍÊÇÔÚ¾ºÈüÖÐÁìÂÔ¹ýËã·¨µÄÓÅÃÀÖ®ºó£¬¿ªÊ¼¶Ô¼ÆËã»ú¿ÆÑ§ÒÔÖÁÊýѧ²úÉúÓÉÖԵľ´Î·ºÍÔÞ̾¡£·´¹ÛÄÇЩËùνµÄÑо¿£¨ÓÈÆäÊÇÔÚ¹úÄÚµÄѧУ£©£¬³ÆµÃÉÏÑо¿·½·¨¡¢Ñо¿Ë¼ÏëµÄÓÖÓжàÉÙÄØ£¿ÔÆÉ½ÎíÕÖ¹ÊŪÐþÐéÀ´ºöÓÆ¾·ÑµÄ¾Í²»ÌáÁË£¬´óѧѧ±¨Á¬Ä³Ð©»ù±¾µÄ¸ÅÄŪ²»¶Ô£¬Çó×î´óÁ÷°Ñ×îÆÓËØµÄford-fulkerson¼Ó¸öÅÄÄÔ´üÏë³öµÄheuristic£¬Ò²²»Ö¤Ã÷һϾ͸ÒÐû³ÆO(VE)µÄ¸´ÔÓ¶È£¬»¹ÓÐʲôµ÷ºÍ¼¶Êý¼ÈÊÕÁ²ÓÖ·¢É¢£¬ÕâÓÖËãÊÇʲôÑо¿·½·¨ÄØ£¿
2. ACMÌâÄ¿ÀïȷʵÓкܶà¿ÉÒÔËã×÷¡°Ææ¼¼¹ÖÇÉ¡±µÄ¶«Î÷£¬µ«ÕâЩ¡°Ææ¼¼¹ÖÇÉ¡±ÕýÊÇÈô¸ÉÄêǰÑо¿ÂÛÎÄÀï·¢±íµÄÄÚÈÝ¡£Êµ¼ÊÉÏΪÁ˽â¾öijЩACMÌ⣬ÎÒÃǾ³£ÒªÈ¥²éÔĹýÈ¥µÄÂÛÎÄ£¬ACMÌâĿֻÊǰÑÂÛÎÄÀïµÄÄÚÈÝ·ÅÔÚÁËÒ»¸öÓÐʵ¼Ê±³¾°µÄÉÏÏÂÎÄÀï¶øÒÑ¡£ÓÃÒ»¸öÇÉÃîµÄÊý¾Ý½á¹¹°Ñijһ²½²Ù×÷´ÓO(n)½µµ½O(logn)£¬Èç¹ûÕâ¸ö½â·¨Ö®Ç°Ã»Óб»·¢±í¹ý£¬ÕâÑùµÄ¡°Ææ¼¼¹ÖÇÉ¡±²»ÕýÊÇÒ»¸ö¾øºÃµÄÂÛÎÄÌâ²Äô£¿ÄѵÀÖ»ÓÐNP£½PÕâÑùµÄ´óÎÊÌâ²ÅÖµµÃÑо¿£¿
3. ÒòΪ°æÉÏÇ°Ãæ¼¸¸öÌû×ÓÌÖÂÛµÄÊ**«Ë¾ÕÐÈ˸ò»¸Ã¿´ÖØACMʲôʲôµÄ£¬ÎҾʹ󵨵شӹ«Ë¾ÕÐÈ˵ĽǶÈ̸һ̸ÕâÊ¡£ÒÔÎҵĹ۲죬ACMer´ó¶¼ÓÐÕâô¼¸¸öÓŵ㣺£¨1£©´ÏÃ÷£¬²¢ÇÒÖªµÀ±È×Ô¼º¸ü´ÏÃ÷µÄÈËÓкܶࡣ´óÑÔ²»²ÑµØ½²£¬Õâ¸ö¾ºÈü»¹ÊÇÐèÒªÒ»µãÖÇÉ̵ģ¬ÒÔÎҵĹ۲죬²Î¼ÓÕâ¸ö±ÈÈüµÄͬѧÔÚ¸Õ¿ªÊ¼Ê±´ó¶¼ÊÇÆÄÓеã×Ô¸ºµÄ£¬µ«ÊDZ»¸÷ÖÖ´óÉñŰ¼¸¶ÙÒÔºó¾Í»áÖªµÀÌìÍâÓÐÌìÁË¡££¨2£©¶Ô¼ÆËã»úÓз¢×ÔÄÚÐĵÄÐËȤ£¬²¢ÇÒÓгÖÖ®ÒÔºãµÄ¾«Éñ¡£´óÌåÀ´½²²Î¼ÓACM¾ºÈüµÄ¹¦ÀûÐÔÊDZȽÏСµÄ£¨µ±È»£¬Ëæ×ÅACM¾ºÈüÔÚ¹úÄÚÔ½À´Ô½Êܵ½ÖØÊÓ£¬²»¿É·ñÈÏÏÖÔÚ¾ºÈüµÄ¹¦ÀûÐÔ±äÇ¿ÁË£©£¬ÒªÏëµÃµ½¸öÏñÑùµÄ³É¼¨£¬Èç¹û²»ÊdzöÓÚÕæÕýµÄÐËȤÊǼá³Ö²»ÏÂÀ´µÄ¡£²»×ö±ÈÈüµÄͬѧƽʱ¿ÉÄÜÒ²µ½OnlineJudgeÉÏËæ±ã×ö¼¸µÀÌ⣬¿ÉÄܾõµÃûʲô´ó²»ÁË£¬µ«ÊDz»ÊÇËùÓÐÈ˶¼ÄÜÓÐÒãÁ¦¼á³Ö¼¸Ä꣬×ö¼¸Ç§µÀÌ⣬дʮ¼¸ÍòÐдúÂë¡£Ì⺣սÊõÄã¿ÉÒÔ²»ÔÞͬ£¬ÆäʵÎÒÒ²²»ÔõôÔÞͬ£¬µ«ÓÐÕâÖÖÒãÁ¦µÄÈËÒ»¶¨ÊÇÓпÉȡ֮´¦µÄ¡££¨3£©»ù±¾¹¦Ôúʵ¡£±à³ÌÓïÑÔ¡¢Ëã·¨¡¢Êý¾Ý½á¹¹ÕâÑùµÄ¿Î³Ì¾Í²»±Ø¶à˵ÁË£¬¸ÅÂÊ¡¢ÀëÉ¢¡¢×éºÏÊýѧµÈµÈÒ²¶¼ÊÇACMerÈÕÒ¹²ÙÁ·ËæÊÖÄéÀ´µÄ¶«Î÷¡£ÒòΪºÜ×¢ÖØ³ÌÐòЧÂÊ£¬ACMerÍùÍùÒ²¶Ô»ã±àÓïÑÔ¡¢²Ù×÷ϵͳ¡¢Ìåϵ½á¹¹µÈ֪ʶÓÐÏà¶Ô¸üÉî¿ÌµÄÀí½â¡£Äã¿ÉÒÔÅúÆÀ˵ACMer´ÓÀ´²»Ð´¹¤³Ì´úÂë¡¢±äÁ¿ÃûËæÒâ¡¢´úÂë·ç¸ñ²»ºÃ¡¢²»¿¼ÂÇÒì³£Çé¿öʲôµÄ£¬µ«ÄÇÖ»ÊÇÒòΪËûÃÇ´Óǰ²»¹Ø×¢ÕâЩ¡£´Ó¹«Ë¾µÄ½Ç¶È¿´£¬¸øÐÂÈËÅàѵ´úÂë¹æ·¶£¬±ÈÆð¸øÐÂÈËÅàѵËã·¨Êý¾Ý½á¹¹µÈµÈÒ»ÕûÌ×»ù±¾ÖªÊ¶£¬Äĸö¸üÈÝÒ×ÄØ£¿Ëµµ½ÕâÀïÎÒ¾õµÃºÜ¶àÈËÓиöÎó½âÐèÒª³ÎÇåһϣºACMer»á×öACMÌ⣬²»´ú±íÈ˼ÒÖ»»á×öACMÌâ¡£Èç¹ûÒ»¸öACMerÄܸ㶨ÄÇô¶à·±¸´¾À½áµÄËã·¨£¬ËûѧÆð¹¤³ÌÐԵĶ«Î÷À´»áºÜÀ§ÄÑô£¿
ÒÔÉÏÊÇÎҲ²⹫˾¿´ÖØACM±ÈÈüµÄ¼¸µã×îÖØÒªÔÒò¡£Ïà±È֮ϣ¬ÄãÊDz»ÊǶ®Ä³¸öËã·¨Õâ¼þʱ¾Éí²¢²»ÊÇÌØ±ðÖØÒªµÄÔÒò¡£¹«Ë¾²»ÊÇÒòΪÄãÇ¡ºÃ¶®Ä³Ð©Ëã·¨¶øÕÐÄ㣬¶øÊÇÒòΪ¶®ÕâЩËã·¨±íÃ÷Äã¸ü¿ÉÄÜÊÇÒ»¸öÓÅÐãµÄÈ˲š£
http://roba.rushcj.com/?p=553