题解 P6082 【[JSOI2015]salesman】

HH_Halo · 2020-10-12 17:18:34 · 题解

另一种食用方式

思路分析

• 题目说的非常磨叽。我们先来读题，这很重要。首先任意两个城镇之间都只有唯一的路线，说明这是一棵树。停留一次就饱和，说明每个点的点权只能获得一次，即使经过多次。还有一个很重要的一点，这是一个巡回，也就是说最后要再次回到根节点，是一个来回，每个节点只要向其子节点走，就一定还会再回来，耗费一次停留次数。(最后一点必须get到)
• 而停留次数只会在上面提到的过程中消耗，不可能出现跑回父节点再跑回来的可能，显然这样是白白耗费了次数而没有任何收益
• 到这里大体的模型就已经出来了。每个点的停留次数 -1(因为最初到达这个节点耗费了一次停留次数)就是最多的到达其子节点的次数(这里有的题解说是子树，显然是有缺陷的)。到达子节点后就可以继续像这样递归处理。
• 然后根据贪心思想，对所有以子节点为根的收益排序(用一个优先队列就够了)，最多选 该节点的停留次数 -1 个 。因为有负数，所以不一定要选满

• 最后就是判断是否有多解了，因为题目说了与路径无关，所以只需考虑收益的大小，只有两种情况:

  1. 以某个节点为根的收益大小为0,可选可不选
  2. 再排好序选完以后，没有选的子节点中存在和以及选了的相同的，可以2选1

     Code

     #include<cstdio>
     #include<cstring>
     #include<cmath>
     #include<algorithm>
     #include<queue>
     #include<map>
     #define R register
     #define N 500010
     using namespace std;
     inline int read(){
     int x = 0,f = 1;
     char ch = getchar();
     while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
     return x*f;
     }
     int n,v[N],c[N],f[N],head[N];
     bool flag;
     struct edge{
     int to,next;
     }e[N<<1];
     int len;
     void addedge(int u,int v){
     e[++len].to = v;
     e[len].next = head[u];
     head[u] = len;
     }
     int dfs(int u,int fa){
     priority_queue<int>q;
     map<int,int>vis;//用于多解的情况2
     f[u] = v[u];
     for(R int i = head[u];i;i = e[i].next){
     int v = e[i].to;
     if(v==fa)continue;
     int tmp = dfs(v,u);
     q.push(tmp);
     }
     int cnt = 0,last = 0;
     while(!q.empty()){
     if(cnt==c[u]-1)break;
     int x = q.top();q.pop();
     if(x<0)break;
     last = x;
     f[u] += x;
     vis[x] = 1;
     cnt++;
     }
     if(!q.empty()){
     int x = q.top();
     if(vis[x])flag = 1;//多解的情况2
     }
     if(f[u]==0)flag = 1;//多解的情况1
     return f[u];
     }
     int main(){
     n = read();
     for(R int i = 2;i <= n;i++)v[i] = read();
     for(R int i = 2;i <= n;i++)c[i] = read();
     for(R int i = 1;i < n;i++){
     int x = read(),y = read();
     addedge(x,y),addedge(y,x);
     }
     c[1] = 0x3f3f3f3f;//根节点随便停留
     dfs(1,0);
     printf("%d\n",f[1]);
     if(flag)puts("solution is not unique");
     else puts("solution is unique");
     return 0;
     }