Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

求最大,逆向思维,从最小的求。

Posted by moorage at 2011-04-16 01:10:36 on Problem 2531 and last updated at 2011-04-16 01:11:00
In Reply To:一个剪枝16ms,0ms是怎么出来的? Posted by:openxxx at 2010-02-21 13:33:32
// poj 2531 Network Saboteur
/*
  求最大,逆向思维,从最小的求。
  思考:对于花费最大的集合A和B,在A和B各自内部的花费和必然最小,如果不是最小,外部最大花费还可以据需增加的。
  所以可以求出集合最小内部花费,然后以总花费减去最小花费即可。
我是参考这个写出来的,但是不知道为什么我的程序跑了47ms
*/
#include <stdio.h>
#include <string.h>

const bool A = true;
const bool B = false;

int c[32][32];
int in[32], out[32];
int n, ans, sum, p;
bool set[32];

void dfs(int k, int s, int ni, int no) // A B 集合内部最小花费
{
    if (s > ans)
        return;
    
    if (k >= n){
        if (s < ans)
            ans = s;
        return;
    }
    
    int t = 0;
    in[ni] = k;
    for (int i = 0; i < ni; i++){
        t += c[in[i]][k];
    }
    dfs(k+1, s+t, ni+1, no);

    t = 0;
    out[no] = k;
    for (int i = 0; i < no; i++){
        t += c[out[i]][k];
    }
    dfs(k+1, s+t, ni, no+1);

}

int main()
{
    scanf("%d", &n);
    sum = 0;
    for (int i = 0; i < n ; i++)
        for (int j = 0; j < n; j++){
            scanf("%d", &c[i][j]);
            sum += c[i][j];
        }
    sum /= 2;
    // 取1..n/2 和 1+n/2..n作为一个最小内部花费界限范围
    p = 0;
    for (int i = 0; i < n/2; i++){
        for (int j = 0; j < n/2; j++)
            p += c[i][j];
    }
    for (int i = n/2; i < n; i++){
        for (int j = n/2; j < n; j++)
            p += c[i][j];
    }
    p /= 2;
    
    ans = p;
    in[0] = 0;
    dfs(1, 0, 1, 0);
    
    printf("%d\n", sum - ans);
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


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