现在的位置: 首页 > 综合 > 正文

ZOJ 3715 Kindergarten Election(枚举+贪心)

2014年09月05日 ⁄ 综合 ⁄ 共 3306字 ⁄ 字号 评论关闭

今天练习赛的一个题目,做的时候错了N边,sad啊、、贪心的时候贪错了啊。我是这么贪的,把得到的选票进行排序。然后判断第一个人的的票的多少与最多的的票的差距。然后从所有的里面选择新的糖果数少的,加入。这样贪心的话,会出现错误。比如说第一个比最大的一个少1票。如果从最大的里面拿出一票给第一个的值小于从其他的地方拿来两个的值小的话。这么贪心就出现错误了啊。

正确的方法是:由于这里的n比较小,我们只要枚举1当班长时的得票数x,然后再将其他人的得票数大于x的变为x-1  (减少的给1并且减少的肯定是所需糖果树最少的),然后检查最后1的得票数,如果大于x那么肯定无解,如果等于x,只要保证2到n中有得票数<= x - 2的即可。如果小于x,那么从剩下没有支持1的中,找出所需糖果树最少的来贿赂得票知道等于x为止。


Kindergarten Election


Time Limit: 2 Seconds      Memory Limit: 65536 KB


At the beginning of the semester in kindergarten, the n little kids (indexed from 1 to n, for convenience) in class need to elect their new leader.

The ith kid will vote for his best friend fi (where 1 ≤ fi ≤ n, and it's too shame to vote for yourself, so fi ≠
i
). And the kid who gets the most votes will be the leader. If more than one kids who get the largest number of votes, there will be multiple leaders in the new semester.

Little Sheldon (the kid with index 1) is extremely vain, and he would like to be the ONLY leader. (That means the number of votes he gets should strictly larger than
any other.) Soon Sheldon found that if he give ci candies to the ith kid, the ith kid would regard Sheldon as the new best friend, and of course vote for Sheldon.

Every kid including Sheldon loves candies. As an evil programmer, please help the evil Sheldon become the ONLY leader with minimum cost of candies. By the way, Sheldon
should vote for any one he wants EXCEPT himself.

Input

There are multiple test cases. The first line of input contains an integer T (T ≤ 100) indicating the number of test cases. Then T test cases follow.

The first line of each case contains one integer: n (3 ≤ n ≤ 100) -- the number of kids in class.

The second line contains n-1 integers: fi (1 ≤ fi ≤ nfi ≠ i, and 2 ≤ i ≤ n) -- represents that the best
friend of ith kid is indexed with fi.

The third line contains n-1 integers: ci (1 ≤ ci ≤ 1000, and 2 ≤ i ≤ n) -- represents that if Sheldon gave ci candies
to the ith kid, the ith kid would vote Sheldon, instead of their old best friend fi, as the new semester leader.

Output

For each test case, print the minimal cost of candies to help Sheldon become the ONLY leader.

Sample Input

2
4
1 1 2
1 10 100
3
3 2
1 10

Sample Output

0
11

Hint

In the first case,

  • If Sheldon vote for 2nd kid, the 2nd kid and Sheldon will both have 2 votes. In this case, Sheldon have to pay 100 candies to the 4th kid, and get 3 votes to win;
  • If Sheldon vote for 3rd or 4th kid, Sheldon will win with 2 votes without sacrifice any candy.
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-7
#define M 1000100
#define LL __int64
#define INF 0x3f3f3f3f
#define PI 3.1415926535898

const int maxn = 110;
using namespace std;

int mp[maxn][maxn];
int vote[maxn], c[maxn], b[maxn];
int ans, res;
int vt1[maxn], vt2[maxn];
int n;

int get(int k)
{
    for(int i = 2; i <= n; i++)
    {
        if(b[i] >= k)
        {
            while(b[i] != k-1)
            {
                int t1 = 0;
                int t2 = INF;
                for(int j = 2; j <= n; j++)
                {
                    if(mp[j][i] && !vt2[j] && c[j] < t2)
                    {
                        t2 = c[j];
                        t1 = j;
                    }
                }
                ans += t2;
                vt2[t1] = 1;
                b[i]--;
                b[1]++;
            }
        }
    }
    return b[1];
}

int main()
{
    int T;
    cin >>T;
    while(T--)
    {
        cin >>n;
        memset(vote, 0 , sizeof(vote));
        memset(vt1, 0 , sizeof(vt1));
        memset(mp, 0 , sizeof(mp));
        for(int i = 2; i <= n; i++)
        {
            int x;
            cin >>x;
            vote[x]++;
            mp[i][x] = 1;
            if(x == 1)
                vt1[x] = 1;
        }
        for(int i = 2; i <= n; i++)
            cin >>c[i];
        res = INF;
        for(int k = vote[1]; k <= n; k++)
        {
            if(k <= 1) continue;
            for(int i = 1; i <= n; i++) vt2[i] = vt1[i];
            for(int i = 1; i <= n; i++) b[i] = vote[i];
            ans = 0;

            int f = get(k);
            if(f == k)
            {
                int j;
                for(j = 2; j <= n; j++)
                    if(b[j] <= k-2)
                        break;
                if(j <= n)
                    res = min(res,ans);
            }
            else
            {
                while(f < k)
                {
                    int t1 = 0;
                    int t2 = INF;
                    for(int i = 2; i <= n; i++)
                    {
                        if(!vt2[i] && c[i] < t2)
                        {
                            t2 = c[i];
                            t1 = i;
                        }
                    }
                    vt2[t1] = 1;
                    ans += t2;
                    f++;
                }
                res = min(res, ans);
            }
        }
        cout<<res<<endl;
    }
    return 0;
}


抱歉!评论已关闭.