首页 > ACM题库 > HDU-杭电 > HDU 2790-HOJ-Safe Gambling-最小生成树-[解题报告]C++
2014
02-14

HDU 2790-HOJ-Safe Gambling-最小生成树-[解题报告]C++

Safe Gambling

问题描述 :

All banks and other financial institutions want their money to earn other money. It is really simple: they invest in some assets (such as stocks), wait until their value grows, and then sell them with a high profit.

Due to the crisis, the stock exchange rates change too quickly, which caused the stocks to become too risky assets. Since large and creditable banks cannot afford so much risk, they have to search for other activities that bring similar profit but that are more predictable. Such as betting the money in casinos.

You were asked by a manager of one important bank (whose name has to be kept secret, since this is a highly confidential matter) to develop a computer program that would help them to "invest" their money into a new modern roulette, operated by Casino Vater Und Tochter (CVUT).

The roulette is an unusual one. Each pocket ("number") may have a different price that must be paid when that particular number is used in a bet. Moreover, any bet in this roulette must simultaneously cover only adjacent pockets. The price of such a bet is the sum of prices for individual pockets.

Bank managers made a decision that in every bet, one half of the pockets must be covered. They supposed that if two such bets are made, all pockets will be covered and there will be absolutely no risk of losing. But they did not realize that croupiers also have to earn some money. This is why the number zero was introduced into roulettes. Therefore, the total number of pockets is always odd and two bets are not enough to cover all of them (there would always be one pocket left).

To eliminate any risks, it was decided that two bets are not enough. In each game, three bets must be made instead of two, to cover all existing pockets. Your task is to compute the minimal price of such bets.

输入:

The input contains description of several roulettes. Each roulette description consists of two lines. The first line contains a single positive odd integer N = 2 * K + 1 (3 ≤ N < 200000), the number of roulette pockets.

The second line contains N positive integers separated by a space, denoting the price of individual pockets, in the order they appear on the circumference of the wheel. The last pocket is supposed to neighbor with the first one. All prices will be between zero and 1000.

The last roulette description is followed by a line containing zero.

输出:

The input contains description of several roulettes. Each roulette description consists of two lines. The first line contains a single positive odd integer N = 2 * K + 1 (3 ≤ N < 200000), the number of roulette pockets.

The second line contains N positive integers separated by a space, denoting the price of individual pockets, in the order they appear on the circumference of the wheel. The last pocket is supposed to neighbor with the first one. All prices will be between zero and 1000.

The last roulette description is followed by a line containing zero.

样例输入:

5
1 2 3 4 5
9
1 2 3 4 5 6 7 8 9
0

样例输出:

16
51

题意就是按照边的权构造最小生成树,如果有生成树代表图是连通的,否则输出No solution.

然后将剩下的M-(N-1)条边加入生成树,统计点的次数,输出即可。

Runid Proid Subtime Judgestatus Runtime Memory Language Code Length Author
503906 2790 2010-08-16 19:55:57 Accepted 0.03 s 1276 K C++ 1895 B luyi0619
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#define inf 0x7fffffff
using namespace std;
struct edge
{
    int u,v,flag;
    bool operator >(const edge e) const
    {
        return u<e.u || u==e.u && v<e.v;
    }
};
edge edg;
vector<edge> ivec;
int mat[51][51],root[51],times[51];
int getf(int x)
{
    if(x==root[x])
        return root[x];
    else
        return root[x]=getf(root[x]);
}
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)==2)
    {
        memset(times,0,sizeof(times));
        for(int i=0; i<=n; i++)
            root[i]=i;
        ivec.clear();
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                scanf("%1d",&mat[i][j]);
        for(int i=0; i<n; i++)
        {
            for(int j=i+1; j<n; j++)
            {
                if(mat[i][j])
                {
                    edg.u=i;
                    edg.v=j;
                    edg.flag=0;
                    ivec.push_back(edg);
                }
            }
        }
        if(ivec.size()<m)
        {
            printf("No solution.\n");
            continue;
        }
        sort(ivec.begin(),ivec.end(),greater<edge>());
        int cnt=0;
        for(vector<edge>::iterator p=ivec.begin(); p!=ivec.end(); p++)
        {
            int f1=getf(p->u),f2=getf(p->v);
            if(f1!=f2)
            {
                cnt++;
                root[f1]=f2;
                times[p->v]++;
                times[p->u]++;
                p->flag=true;
            }
        }
        if(cnt!=n-1)
        {
            printf("No solution.\n");
            continue;
        }
        for(vector<edge>::iterator p=ivec.begin(); p!=ivec.end(); p++)
        {
            if(!p->flag)
            {
                times[p->v]++;
                times[p->u]++;
                cnt++;
            }
            if(cnt == m)
                break;
        }
        if(cnt == m)
        {
            for(int i=0; i<n; i++)
            {
                if(i)
                    printf(" ");
                printf("%d",times[i]);
            }
            printf("\n");
        }
        else
            printf("No solution.\n");
    }
    return 0;
}

解题参考:http://www.cnblogs.com/luyi0619/archive/2010/08/16/1800971.html


  1. 看到演蜘蛛侠的父亲,哭了,心酸……看到如何解决“随便”的女友,又笑了!这特么的也转变的太快了吧?!也不给人缓冲一下……

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!