首页 > ACM题库 > HDU-杭电 > HDU 3027-Network[解题报告]HOJ
2014
02-27

HDU 3027-Network[解题报告]HOJ

Network

问题描述 :

There is a network which is a completely binary tree. In the network, there are 2N users numbered from 1, 2, 3, 4, … 2N, which are the leaves in the network-tree. For example, Figure 1 is a network-tree. In the tree, there are 8 users (leaf nodes) and 7 transmitters (gray nodes).
 Chinese Chess

Using network-tree means that you have to pay a cost for it. The charging way is so interesting, named "pair charging". The cost you must pay is the sum of cost from every pair of user i and user j ( 1 ≤ i < j ≤ 2N). Every user can choose mode A or mode B to pay for the charge.

For every two users i, j (1 ≤ i < j ≤ 2N), first find their LCA (The Least Common Ancestors): Transmitter P. Then count the number of mode A users in the tree of ROOT transmitter P, so do mode B.

Next, let’s name the number nA and nB and at last charge the cost.

f[i][j] is the flow between user i and user j.

The charging way is followed:

 Chinese Chess

At first, every user has an initial mode, A or B. However, they want to reduce the cost, so a part of them would change the mode from A to B, or from B to A. Every change will have an extra cost. If user i changes his mode, he will pay Ci cost.

Now, you should find the minimum cost, that is, the sum of the cost having to pay for and the extra cost of changing mode.

输入:

First line, an integer N (N ≤ 10).

Sencond line, 2N integers, ith integer stands for ith user’s initial mode. 0 is mode A, 1 is mode B.

Third line, 2N integers, ith integer stands for Ci, the cost that ith user changes his mode. (0 ≤ Ci ≤ 500 000)

Next 2N – 1 line, describe the flow of every pair of users. The i + 3 th line’s (in the whole input) j row’s integer standing for the f[i][j + i]. (1 ≤ i ≤ 2^N ,1 ≤ j ≤ 2^N – i, 0 ≤ f[i][j] ≤ 500).

输出:

First line, an integer N (N ≤ 10).

Sencond line, 2N integers, ith integer stands for ith user’s initial mode. 0 is mode A, 1 is mode B.

Third line, 2N integers, ith integer stands for Ci, the cost that ith user changes his mode. (0 ≤ Ci ≤ 500 000)

Next 2N – 1 line, describe the flow of every pair of users. The i + 3 th line’s (in the whole input) j row’s integer standing for the f[i][j + i]. (1 ≤ i ≤ 2^N ,1 ≤ j ≤ 2^N – i, 0 ≤ f[i][j] ≤ 500).

样例输入:

2 
1 0 1 0 
2 2 10 9
10 1 2 
2 1 
3

样例输出:

8

Explanation: Changing the user 1's mode from B to A will minimumize the cost. 

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<map>
#include<string>
#include<algorithm>
using namespace std;

#define eps 1e-12
#define maxn 1100
#define maxm 1100000
#define inf 0x3f3f3f3f
#define PB push_back
#define MP make_pair

typedef struct{
    int len,sta;
}node;
node r[10],t[10];
int next[10][70000],pck[1010][3];
int mp[120][5];
bool f[5];
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n,m,i,j,k,l,p,q,ans,tmp,now,cnt=1;
    memset(f,true,sizeof(f));
    i=0;
    for(j=0;j<5;j++)
    {
        f[j]=false;
        for(k=0;k<5;k++)
            if(f[k])
            {
                f[k]=false;
                for(l=0;l<5;l++)
                    if(f[l])
                    {
                        f[l]=false;
                        for(p=0;p<5;p++)
                            if(f[p])
                            {
                                f[p]=false;
                                for(q=0;q<5;q++)
                                    if(f[q])
                                    {
                                        mp[i][0]=j;
                                        mp[i][1]=k;
                                        mp[i][2]=l;
                                        mp[i][3]=p;
                                        mp[i][4]=q;
                                        i++;
                                    }
                                f[p]=true;
                            }
                        f[l]=true;
                    }
                f[k]=true;
            }
        f[j]=true;
    }
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        for(i=0;i<n;i++)
        {
            scanf("%d",&r[i].len);
            r[i].sta=1;
        }
        for(i=0;i<m;i++)
        {
            scanf("%d %d %d",&pck[i][0],&pck[i][1],&pck[i][2]);
            pck[i][0]--;
        }
        ans=1000000000;
        for(i=0;i<120;i++)
        {
            memcpy(t,r,sizeof(node)*10);
            memset(next,0,sizeof(next));
            tmp=now=0;
            for(j=0;j<n;j++) f[j]=true;
            for(;j<5;j++) f[j]=false;
            for(j=0;j<5;j++)
                if(f[mp[i][j]])
                {
                    p=mp[i][j];
                    break;
                }
            for(k=0;k<m;k++)
            {
                next[pck[k][0]][pck[k][1]]=pck[k][2];
                if(pck[k][0]==p&&pck[k][1]==t[p].sta)
                {
                    for(q=pck[k][2]+1;next[p][q];q=next[p][q]+1);
                    now-=(q-pck[k][2]-1);
                    t[p].sta=q;
                    if(q<=t[p].len) continue;
                    f[p]=false;
                    while(1)
                    {
                        for(j+=1;j<5;j++)
                            if(f[mp[i][j]])
                            {
                                p=mp[i][j];
                                break;
                            }
                        if(j==5) break;
                        for(q=1;next[p][q];q=next[p][q]+1);
                        now-=(q-t[p].sta);
                        t[p].sta=q;
                        if(q<=t[p].len) break;
                        f[p]=false;
                    }
                }
                else{
                    now+=(pck[k][2]-pck[k][1]+1);
                    tmp=max(tmp,now);
                }
            }
            ans=min(ans,tmp);
        }
        printf("Case %d: %d\n\n",cnt++,ans);
    }
}

  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.