首页 > ACM题库 > HDU-杭电 > HDU 3268-Columbus’s bargain-最短路径-[解题报告]HOJ
2014
03-13

HDU 3268-Columbus’s bargain-最短路径-[解题报告]HOJ

Columbus’s bargain

问题描述 :

On the evening of 3 August 1492, Christopher Columbus departed from Palos de la Frontera with a few ships, starting a serious of voyages of finding a new route to India. As you know, just in those voyages, Columbus discovered the America continent which he thought was India.

Because the ships are not large enough and there are seldom harbors in his route, Columbus had to buy food and other necessary things from savages. Gold coins were the most popular currency in the world at that time and savages also accept them. Columbus wanted to buy N kinds of goods from savages, and each kind of goods has a price in gold coins. Columbus brought enough glass beads with him, because he knew that for savages, a glass bead is as valuable as a gold coin. Columbus could buy an item he need only in four ways below:

1.  Pay the price all by gold coins.
2.  Pay by ONE glass bead and some gold coins. In this way, if an item’s price is k gold coins, Columbus could just pay k � 1 gold coins and one glass bead.
3.  Pay by an item which has the same price.
4.  Pay by a cheaper item and some gold coins.

Columbus found out an interesting thing in the trade rule of savages: For some kinds of goods, when the buyer wanted to buy an item by paying a cheaper item and some gold coins, he didn’t have to pay the price difference, he can pay less. If one could buy an item of kind A by paying a cheaper item of kind B plus some gold coins less than the price difference between B and A, Columbus called that there was a “bargain” between kind B and kind A. To get an item, Columbus didn’t have to spend gold coins as many as its price because he could use glass beads or took full advantages of “bargains”. So Columbus wanted to know, for any kind of goods, at least how many gold coins he had to spend in order to get one � Columbus called it “actual price” of that kind of goods.

Just for curiosity, Columbus also wanted to know, how many kinds of goods are there whose “actual price” was equal to the sum of “actual price” of other two kinds.

输入:

There are several test cases.
The first line in the input is an integer T indicating the number of test cases ( 0 < T <= 10).
For each test case:
The first line contains an integer N, meaning there are N kinds of goods ( 0 < N <= 20). These N kinds are numbered from 1 to N.

Then N lines follow, each contains two integers Q and P, meaning that the price of the goods of kind Q is P. ( 0 <Q <=N, 0 < P <= 30 )
The next line is a integer M( 0 < M <= 20 ), meaning there are M “bargains”.

Then M lines follow, each contains three integers N1, N2 and R, meaning that you can get an item of kind N2 by paying an item of kind N1 plus R gold coins. It’s guaranteed that the goods of kind N1 is cheaper than the goods of kind N2 and R is none negative and less than the price difference between the goods of kind N2 and kind N1. Please note that R could be zero.

输出:

There are several test cases.
The first line in the input is an integer T indicating the number of test cases ( 0 < T <= 10).
For each test case:
The first line contains an integer N, meaning there are N kinds of goods ( 0 < N <= 20). These N kinds are numbered from 1 to N.

Then N lines follow, each contains two integers Q and P, meaning that the price of the goods of kind Q is P. ( 0 <Q <=N, 0 < P <= 30 )
The next line is a integer M( 0 < M <= 20 ), meaning there are M “bargains”.

Then M lines follow, each contains three integers N1, N2 and R, meaning that you can get an item of kind N2 by paying an item of kind N1 plus R gold coins. It’s guaranteed that the goods of kind N1 is cheaper than the goods of kind N2 and R is none negative and less than the price difference between the goods of kind N2 and kind N1. Please note that R could be zero.

样例输入:

1
4
1 4
2 9
3 5
4 13
2
1 2 3
3 4 6

样例输出:

1 3
2 6
3 4
4 10
1

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3268

这是一个最短路的问题,建立一个源点S,然后连接所有的点,边上的权值为最初的价钱p-1,可用来交易的物品建边,权值为R,然后价钱相等的物品建边,权值为0,求以S为源点的单源多点最短路,即可求出结果,第二问三重循环可求解,注意第二问循环的判断条件,勿让物品选重复。。。,这里wa了好久。。代码参考:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

#define CLR(arr,v) memset(arr,v,sizeof(arr))

int m,n;
const int size = 50;
const int INS = INT_MAX/2;
int val[size],dis[size];
int h[size],ed[1000],nex[1000],price[1000],que[size],inque[size];
int pos,head,total;

void init()
{
    pos = 1;head = total = 0;
    CLR(h,0); CLR(que,0);  CLR(price,0);
    CLR(ed,0);CLR(inque,0);CLR(nex,0);
    fill(dis,dis+size,INS);CLR(val,0);
}
void add(int u,int v,int f)
{
    ed[pos] = v;
    price[pos] = f;
    nex[pos] = h[u];
    h[u] = pos++;
}

void SPFA()
{
    dis[0] = 0;
    que[total++] = 0;
    inque[0] = true;
    while(head < total)
    {
        int p = que[head];    
        inque[p] = false;
        head = (head+1)%size;
        for(int i = h[p]; i ;i = nex[i])
        {
            int to = ed[i];
            if(dis[to] > dis[p] + price[i])
            {
                dis[to] = dis[p] + price[i];
                if(!inque[to])
                {
                    que[total] = to;
                    inque[to] = true;
                    total = (total+1)%size;
                }
            }
        }
    }
    for(int i = 1;i <= n;++i)
    {
        printf("%d %d\n",i,dis[i]);
    }
    int cnt = 0; CLR(val,0);
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= n;++j)
            for(int k = 1 + j;k <= n;++k)
                if(i != j && i != k && dis[i] == dis[k] + dis[j] && !val[i])
                {
                    val[i] = true;cnt++;
                }
    printf("%d\n",cnt);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d",&n);
        int b,money;
        for(int i = 1;i <= n;++i)
        {
            scanf("%d%d",&b,&money);
            val[b] = money;
            add(0,b,money-1);
        }
        scanf("%d",&m);
        int u,v,f;
        for(int i = 0;i < m;++i)
        {
            scanf("%d%d%d",&u,&v,&f);
            add(u,v,f);
        }
        for(int i = 1;i <= n;++i)
            for(int j = 1;j <= n;++j)
                if(i != j && val[i] == val[j])
                {
                    add(i,j,0);
                    add(j,i,0);
                }
        SPFA();
    }
    return 0;
}

参考:http://blog.csdn.net/fire__ice/article/details/7353430