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

这个题，特像最大流中找最小切（割），是不是用网络流也能做？

Posted by sunmoonstar_love at 2005-08-06 15:26:34 on Problem 2531

Followed by:

这个是最大割 (0) frkstyc 2005-08-06 15:29:17
- 嗯，有找最大割的好方法么？ (0) sunmoonstar_love 2005-08-06 15:31:09
  - 最小割==最大流？？不是么？ (0) sunmoonstar_love 2005-08-06 15:31:46
    - 但显然没有最大割=最小流的东西 (0) frkstyc 2005-08-06 15:32:13
最大割是NP-Hard (0) frkstyc 2005-08-06 15:36:49
- 。。。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