Campaign Stops （拉票） -- 编程驿站-- 编程爱好者博客

Campaign Stops

Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB

Total submit users: 18, Accepted users: 15

Problem 10924 : No special judgement

Problem description

One of the important parts of running an election year campaign is to go lots of places, give your carefully crafted stump speech, and convince a lot of potential voters to vote for you. Unfortunately, there are only so many hours in the day, so you cannot go everywhere. So you need to plan your campaign trips carefully, trading off between travel time, time spent at the stops, and the number of voters you are going to sway. Better have a computer do the planning for you.

We assume that for each potential campaign stop, you are given the number of voters you expect to sway by appearing there, and the number of hours you would have to spend at the location. In addition, for each pair of stops, you are given the travel time from one to the other. If you also know the number of hours you have available, you can now optimize to sway as many voters as possible.

Input

    The first line contains a number K ≥ 1, which is the number of input data sets. This is followed by K data sets of the following form:

    The rst line of each data set contains two number n and H. Here, 1 ≤ n ≤ 10 is the number of candidate campaign stops, and 1:0 ≤ H ≤ 24:0 is the number of hours you have available (this may be a fractional number).

    This is followed first by n lines, each describing a campaign stop, by giving two numbers, an integer v_i ≥ 0, and a fractional number h_i ≥ 0. v_i is the number of voters you could sway at that stop, and h_i the number of hours you'd have to spend there.

    Finally, this is followed by n more lines, each containing n numbers, where the j^th number of line i is a fractional number, the number of hours it takes to travel from city i to city j. (Thus, the i^th number of line i is 0, but it is not necessarily the case that the travel time from city i to city j is the same as from city j to city i.)

Output

For each data set, first output "Data Set x:" on a line by itself, where x is its number. Then, output the maximum number of voters that can be swayed during the available time H. Assume that the candidate's tour always starts at city 1, and has to return there, although he may not have to campaign there.

Sample Input

1
4 13.5
100 3.5
100 1.0
300 4.0
140 5.0
0.0 1.0 4.0 1.5
1.0 0.0 5.0 0.5
5.0 5.0 0.0 5.5
2.0 0.7 5.0 0.0

Sample Output

Data Set 1:
340

Problem Source

USC 2006 Spring

题目大意：为竞争某个职位（特别是美国总统，拉票超厉害）我们需要都一些城市巡回演讲（停留），这些城市两两相连，从 a到 b 所发的时间与从 b 到 a 的时间可能不同，每个城市如果停留一定时间，我们就假设能够获得预期的选票，首先输入用例数目第二行输入城市数目和我们拥有的时间，之后是选票和停留时间。以及各城市之间来往所需的时间表。我们必须在巡回完后回到起始城市，起始城市总是 1。

优先搜索加分支限界：

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

typedef pair< pair<int,int>,float> TYPE_FIRST;
const int CITYS = 10, SELECT_MAX = 20;
int   gFirst[CITYS][CITYS],gBestResult,gCount;
float gInfo[CITYS][CITYS], gretTime[CITYS];
bool gbExpended[CITYS];
pair<int,float> gp[CITYS];

class less_cmp{
public:
    bool operator()(const TYPE_FIRST &a,const TYPE_FIRST &b){
        if(a.second == b.second)
            return a.first.second > b.first.second;
        return a.second < b.second;
    }
};

void getMinTime(int min, int m){
    vector<int> v;
    v.push_back(min);
    for(int j; v.empty()==false; ){
        j = v.back();
        v.pop_back();
        for(int i=0; i<m; i++)
            if(gInfo[i][j]+gretTime[j] < gretTime[i]){
                gretTime[i] = gInfo[i][j] + gretTime[j];
                v.push_back(i);
            }
    }
}

void getFirst(int m){
    vector<TYPE_FIRST>  pp;
    pp.resize(m);
    for(int i=0; i<m; i++){
        for(int j=0; j<m; j++){
            pp[j].first.first = j;
            if(j==i){
                pp[j].first.second = 0;
                pp[j].second = 24;
                continue;
            }
            pp[j].first.second = gp[j].first;
            pp[j].second = gretTime[j]+gInfo[i][j];
        }
        sort(pp.begin(),pp.end(),less_cmp());
        for(int j=0; j<m; j++)
            gFirst[i][j] = pp[j].first.first;
    }
}

void getBestResult(int s, int m, int tbest, float tleft){
    int i,t;
    float ftime;
    if(tleft>gretTime[s]+gp[s].second && tbest+gp[s].first>gBestResult){
        gBestResult = tbest+gp[s].first;
        gCount++;
    }
    if(gCount > SELECT_MAX)
        return ;
    gbExpended[s] = true;
    for(i=0; i<m; i++){
        t = gFirst[s][i];
        if( !gbExpended[t] ){    
            ftime = gInfo[s][t]+gretTime[t];
            if(ftime < tleft )
                getBestResult(t,m,tbest,tleft-gInfo[s][t]);
            if(ftime + gp[s].second < tleft)
                getBestResult(t,m,tbest+gp[s].first,tleft-gInfo[s][t]-gp[s].second);
        }
    }        
    gbExpended[s] = false;    
}

int main(){
    int nTest,m;
    float gTime;
    cin>>nTest;
    for(int i=1; i<=nTest; i++){
        cin>>m>>gTime;
        for(int j=0; j<m; j++)
            cin>>gp[j].first>>gp[j].second;
        int min=1;
        gInfo[1][0] = 24;
        for(int j=0; j<m; j++){
            cin>>gInfo[j][0];
            if(gInfo[j][0] < gInfo[min][0] && min!=0)
                min = j;
            gretTime[j] = gInfo[j][0];
            gbExpended[j] = false;
            for(int i=1; i<m; i++)
                cin>>gInfo[j][i];
        }
        getMinTime(min,m);
        getFirst(m);
        gCount = gBestResult = 0;
        getBestResult(0,m,0,gTime);
        cout<<"Data Set "<<i<<':'<<endl<<gBestResult<<endl;
    }
    return 0;
}

137955

MSN (2)

GNU C++

1212KB

203ms

2468B

虽然过了，也是运气，“ 进化” 20次就搞到正确答案，呵呵可能主要

是因为优先搜索，不知道能不能称为“启发式搜索”。maybe not !!!

博客介绍

正文

Campaign Stops （拉票）2007-08-28 16:24:00

评论