Statement

【IOI2014】Friend - Problem - Universal Online Judge (uoj.ac)

Solution

先观察题目性质 然鹅并没有发现什么性质

题目显然是在问最大权独立集，一个 NP 完全

发现如果没有第三种操作，最后会是一个二分图

我们知道 最大点权独立集=总权值-最小点权覆盖集=总权值-最小割

但是发现数据范围不允许我们跑最大流，而且第三种操作一旦加上就 GG ，需要切换思路

这个题目的破局点在于特殊的连边方式

正难则反，考虑倒着删点（思路来自 p_b_p_b 巨佬，非常 nb

下面简写 \(confidence\to con\quad protocol\to pro\)

Operation 1

两者直接连边，那么显然一者选一者不选，而因为是倒着删点，此时点 \(i\) 只和 \(host[i]\) 有边

我们直接让 \(ans+=con[i],con[host[i]]=max(con[host[i]]-con[i],0)\)

正确性：\(i\) 选不选完全由 \(host[i]\) 决定，可以把 \(i\) 当成一种额外贡献，这种贡献仅在 \(host[i]\) 不选时产生。这样操作，选了 \(host[i]\) ，会增加 \(con[i]+(con[host[i]]-con[i])=con[host[i]]\)

然后直接不管 \(i\) 即可

Operation 2

此时，设 \(host[i]\) 与集合 \(j\) 连边

发现若选 \(j\) ,那么 \(host[i],i\) 都不可选

若不选 \(j\) ,那么二者都要选，所以 \(host[i],i\) 是绑定的

所以直接 \(con[host[i]]+=con[i]\) 即可

Operation 3

仍然设 \(host[i]\) 还与集合 \(j\) 连边

那么，\(p,i\) 若要选，只能选两者之一，区别于操作 1，在于 \(host[i]\) 不选时 \(i\) 不一定选

所以我们让 \(con[host[i]]=max(con[host[i]],con[i])\)

答案即为 \(ans+con[0]\)

Code

//#include "friend.h"
#include<bits/stdc++.h>
using namespace std;

int findSample(int n,int con[],int host[],int pro[]){
    int ans=0;
    for(int i=n-1;i;--i)
        if(pro[i]==0)ans+=con[i],con[host[i]]=max(0,con[host[i]]-con[i]);
        else if(pro[i]==1)con[host[i]]+=con[i];
        else con[host[i]]=max(con[host[i]],con[i]);
    return con[0]+ans;
}

当然，这道题也可以 DP 做 ，其本质也可以理解为对于 \(host[i],i\) 的合并