Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

最大割是NP-Hard

Posted by frkstyc at 2005-08-06 15:36:49 on Problem 2531
In Reply To:这个题，特像最大流中找最小切（割），是不是用网络流也能做？ Posted by:sunmoonstar_love at 2005-08-06 15:26:34

Followed by:

。。。it's impossible (0) sunmoonstar_love 2005-08-06 15:38:08
- 那有什么正规的解法呢？ (0) sunmoonstar_love 2005-08-06 15:39:26
  - local search or dp (0) frkstyc 2005-08-06 15:40:12
    - How to DP?use binary state? (0) zhucheng 2005-08-06 15:41:56
      - enen (0) frkstyc 2005-08-06 15:43:10
        这样不是就没有重复子问题了，相当于枚举吗？ (0) zhucheng 2005-08-06 15:44:33
        状态肯定是枚举的了，重复子问题看怎么理解了 (0) frkstyc 2005-08-06 15:45:26
      - 你怎么做的那么快？？ (0) sunmoonstar_love 2005-08-06 15:44:13
        那么小内存肯定搜的了 (0) frkstyc 2005-08-06 15:44:45
        搜的比我们快十倍 (0) sunmoonstar_love 2005-08-06 15:45:08
        complete search=enumration (0) frkstyc 2005-08-06 15:45:43
        yes， enum (0) sunmoonstar_love 2005-08-06 15:46:34
        对这道题来说dp没有意义，时间复杂度不会降低。 (0) zhucheng 2005-08-06 15:47:10
        我是能不写dfs就尽量不写的…… (0) frkstyc 2005-08-06 15:48:02
        我是搜的，加了一点剪枝。 (0) zhucheng 2005-08-06 15:45:25
  - or greedy APPROXIMATION (0) frkstyc 2005-08-06 15:40:40

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator