6.18训练日记

每天起床第一句,先给自己打个气。 今天的我也要好好训练 鸽了好久的训练,沉迷了两天游戏,及时醒悟过来 本想下一个英雄联盟晚上休息的时候玩玩,看来是没有这个福分了.

P2515 [HAOI2010]软件安装

链接 思路:很快发现,对于一个SCC来说,里面的点要么选,要么都不选,因为只选其中的一些点,是不能满足题目中的前置条件都满足的. 再观察,这个图很特殊,最多有n条边,而且每个点的入度最多只有1,因为每个软件只依赖于另外一个软件.,我们很快发现,SCC出现后,SCC内的每个点入度至少是1,而原图又要求每个点入度至多为1,意味着SCC内与其他的点一定是割离开来的. 既然这样,把SCC缩成一个点后,连向树根.而且我们发现了,如果至少有一个 D i = 0 D_i=0 Di​=0,那么就会有一个树根,如果没有,就需要建立一个虚的树根去连接. 建模完毕,用 d p ( i , j ) dp(i,j) dp(i,j)表示,考虑以 i i i为根,若使用了 j j j个磁盘空间所能获得最大的价值是多少. 不难发现,是一个树上背包的模型,因为每个结点的状态是一个数组.对于每个节点,需要得到一个数组 d p ( j ) dp(j) dp(j),代表给这个点 j j j个空间得到最大利润是多少. 而物品的描述又是: d p ( v , k ) dp(v,k) dp(v,k),给 k 个 空 间 , 物 品 v 能 带 来 的 最 大 利 润 为 d p ( v , k ) k个空间,物品v能带来的最大利润为dp(v,k) k个空间,物品v能带来的最大利润为dp(v,k) 不要忘了,每个物品只能用一次,转移方程不想写了,就看代码吧(反正也没人看) 反正这题就是缩点后的树上背包,背包类型是n件物品选一个,需要枚举空间再枚举物品,因为物品只能选一个.

#include
using namespace std;
#define int long long
const int maxn = 505;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
int dfn[maxn],dfs_clock=0;int low[maxn];int sccnow[maxn];
stackS;int scc_cnt = 0;
vector G[maxn];
int scc_v[maxn];int scc_w[maxn];
int W[maxn],V[maxn];
void Tarjan(int u){
	dfn[u]=low[u]=++dfs_clock;
	S.push(u);
	for(auto v : G[u]){
		if(!dfn[v]){
			Tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(!sccnow[v]) low[u] =min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		scc_cnt++;
		while(true){
			int x = S.top();S.pop();
			scc_w[scc_cnt] +=W[x];
			scc_v[scc_cnt] +=V[x];
			sccnow[x] = scc_cnt;
			if(x==u) break;
		}
	}
}
void find_scc(int n){
	dfs_clock = 0;
	for(int i=1;i>m;
	for(int i=1;i>W[i];
	for(int i=1;i>V[i];
	for(int i=1;i>D;
		if(D==0) continue;
		G[D].push_back(i);
		edge.push_back({D,i});
	}
	for(int i=0;i