【IOI2014】Friend 题解

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\) 的合并

上一篇:Join从句


下一篇:linux磁盘分区fdisk命令详解