首页 > ACM题库 > HDU-杭电 > hdu 2479 Kingdoms[解题报告]hoj
2014
01-26

hdu 2479 Kingdoms[解题报告]hoj

Kingdoms

问题描述 :

The former king of Gridland — CR — has just passed away, leaving his K sons that all desire the throne. Then the war of succession breaks out and the K-King era begins.
Gridland is a rectangle of N*M, with each grid unit as a city. Each city supports one and only one of the K kings as its leader. Cities supporting the same king will always endeavor to establish a kingdom through fighting the rival, and they will not stop until they establish a kingdom satisfying the following rules:
1. The kingdom is a rectangle on the map.
2. Every city on the Gridland supporting that king should be inside the kingdom.
Sadly, through the process of establishing a kingdom, once the opposite cities find that an overlapping of domain is unavoidable, they will inevitably engage in a conflict.
Sometimes for a temporary benefit a bunch of kings may ally into a party. It is certain that one king can only take part in one party at one time, and the cities following a king will correspondingly support the party he joins.
Rather than fighting each other fiercely, cities supporting the same party cooperate and strive to establish a kingdom of the whole party.
Such kingdoms follow the similar rules:
1. The kingdom is a rectangle on the map.
2. Every city on the Gridland supporting that party should be inside the kingdom.
And the fighting trigger with other kingdoms is exactly the same as the above one.
A established kingdom is called stable if and only if:
1. No city in the kingdom has to fight with another kingdom..
2. If the kingdom stands for a party, the party must never have more than R kings.
Now, your job is to find the largest possible stable kingdom. By ‘largest’ we mean the one with the largest number of cities.

输入:

Input contains multiple cases. Each case consists of:
Line 1:Two integers : N and M (1<= N, M <=1000)
Line 2:Two integers : K and R (1<=K<=1000)
Line 3..N+2: M integers each line. the jth integer on the i+2th line will be between 1 and k, indicating which king that city supports.

输出:

Input contains multiple cases. Each case consists of:
Line 1:Two integers : N and M (1<= N, M <=1000)
Line 2:Two integers : K and R (1<=K<=1000)
Line 3..N+2: M integers each line. the jth integer on the i+2th line will be between 1 and k, indicating which king that city supports.

样例输入:

3 3
5 3
4 1 1
2 3 1
2 2 5
10 10
13 5
1 1 1 4 4 4 4 4 3 11
1 1 1 4 4 4 4 4 11 3
1 1 1 2 2 2 2 2 3 3
1 1 1 2 2 2 2 2 3 11
1 1 1 2 2 2 2 2 11 11
1 1 1 2 2 2 2 2 3 11
1 1 1 6 6 6 7 7 3 3
1 1 1 6 6 6 7 7 3 3
5 5 5 5 10 13 8 12 9 9
5 5 5 5 13 10 8 8 9 9
2 2
2 1
2 2
2 1

样例输出:

1
64
0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
#define LL long long
#define maxn 1<<16
#define mod 1000000007
#define INF 1<<30
int d[maxn],n,m,K;
int ro[maxn][3],p[maxn],vis[maxn];
queue<int>q;
int spfa()
{
    int i,j,st,v,tmp;
    for(i=0;i<(1<<n);i++)d[i]=INF,vis[i]=0;
    q.push(1);d[1]=0;vis[1]=1;
    while(!q.empty())
    {
        st=q.front();q.pop();vis[st]=0;
        for(i=0;i<m;i++)
        {
            if((st&(1<<ro[i][0]))&&(st&(1<<ro[i][1]))) continue;
            if(st&(1<<ro[i][0]))
            {
                tmp=st|(1<<ro[i][1]);
                if(d[tmp]>d[st]+ro[i][2])
                {
                    d[tmp]=d[st]+ro[i][2];
                    if(!vis[tmp]&&d[tmp]<=K)
                    {
                        vis[tmp]=1;
                        q.push(tmp);
                    }
                }
            }
            else if(st&(1<<ro[i][1]))
            {
                tmp=st|(1<<ro[i][0]);
                if(d[tmp]>d[st]+ro[i][2])
                {
                    d[tmp]=d[st]+ro[i][2];
                    if(!vis[tmp]&&d[tmp]<=K)
                    {
                        vis[tmp]=1;
                        q.push(tmp);
                    }
                }
            }
        }
    }
    int ans=0;
    for(i=0;i<(1<<n);i++)if(d[i]<=K)
    {
        int tmp=0;
        for(j=0;j<n;j++)if(i&(1<<j))
            tmp+=p[j];
        ans=max(ans,tmp);
    }
    return ans;
}
int main()
{
    int ncase,i;scanf("%d",&ncase);
    while(ncase--)
    {
        scanf("%d %d %d",&n,&m,&K);
        for(i=0;i<n;i++)scanf("%d",&p[i]);
        for(i=0;i<m;i++)scanf("%d %d %d",&ro[i][0],&ro[i][1],&ro[i][2]);
        for(i=0;i<m;++i)ro[i][0]--,ro[i][1]--;
        printf("%d\n",spfa());
    }
}

  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。