• 题目
• 思路
• 代码

[2021.8集训Day1/JZOJ.4253] 【五校联考7day2】QYQ在艾泽拉斯

题目

思路

题目意思可以这样概括:给一张有向图,每个点有一个权值,可以重复经过同一个点,但权值只计算一次,图分成多个块,每个块与其他块没有连边,你可以选择\(k+1\)个块,对于每个块,可以选择一条路径,使得最终经过的点的权值之和最大.

比较水的一道题,Tarjan缩点+DAG DP 的板子题.

代码

#include <iostream>
#include <cstdio>
#include <map>
#include <queue>
#include <cstring>
#include <algorithm>
#define DEBUG 0

typedef long long lint ;
typedef unsigned long long ulint ;
using std::cout;
using std::printf;
using std::memset;

int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

const int N = 1000010 , M = 10000010;

int n , m , k;
namespace UF {//union-find并查集
	int fa[N];
	int maxval[N];
	void init() {
		for(int i = 1 ; i <= n ;  i++)
			fa[i] = i;
	}
	int findroot(int x) {
		return fa[x] == x ? x : (fa[x] = findroot(fa[x]));
	}
	void uni(int x , int y) {
		if(findroot(x) != findroot(y))
			fa[findroot(x)] = fa[y];
	}
}


std::map <ulint , bool>	check;//其实没必要判重边了,这样判反而会超时爆内存
inline ulint hash(int x , int y) {
	return (ulint)x * (n + 1) + y;
}
struct EDGE {
	int to , nxt;
} ed[M * 2];
int __head[2][N] , *head = __head[0];
void addedge(int x , int y) {
	static int cnt = 0;
	++cnt;
	ed[cnt].to = y , ed[cnt].nxt = head[x] , head[x] = cnt;
}


int isl[N];
int __val[2][N] , *val = __val[0];
int ind[N];

namespace tj {//Tarjan
	int col[N] , dfn[N] , low[N];
	int stack[N] , top;
	int tot;

	void tarjan(int x) {
		static int Time = 0;
		dfn[x] = low[x] = ++Time;
		stack[++top] = x;
		for(int i = head[x] ; i ; i = ed[i].nxt) {
			int to = ed[i].to;
			if(!dfn[to]) {
				tarjan(to);
				if(low[to] < low[x])
					low[x] = low[to];
			} else if(col[to] == 0 && low[x] > low[to])
				low[x] = low[to];
		}
		if(dfn[x] == low[x]) {
			col[x] = ++tot;
			isl[tot] = UF::findroot(x);

			__val[1][tot] += val[x];
			while(stack[top] != x)
				__val[1][tot] += val[stack[top]] , col[stack[top]] = tot , --top;
			--top;
		}
	}
	void rebuild() {
		for(int i = 1 ; i <= n ; i++)
			if(dfn[i] == 0)
				tarjan(i);

		check.clear();
		head = __head[1];
		val = __val[1];
		for(int i = 1 ; i <= n ; i++)
			for(int j = __head[0][i] ; j ; j = ed[j].nxt) {
				int u = col[i] , v = col[ed[j].to];
				if(u == v)
					continue;
//				if(!check[hash(u , v)])
//					check[hash(u , v)] = true , 
					addedge(u , v) , ++ind[v];
			}
		check.clear();
		n = tot;
	}
}


int islval[N];
int max(int x , int y) {
	return x > y ? x : y;
}
void topo() {
	int f[N];
	memset(f , 0 , sizeof(f));

	std::queue <int> q;
	for(int i = 1 ; i <= n ; i++)
		if(ind[i] == 0)
			q.push(i) , f[i] = val[i];
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		islval[isl[u]] = max(islval[isl[u]] , f[u]);
		for(int i = head[u] ; i ; i = ed[i].nxt) {
			int v = ed[i].to;
			f[v] = max(f[v] , f[u] + val[v]);
			if(--ind[v] == 0)
				q.push(v);
		}
	}
}
int GetAns() {
	int tmp[N] , size = 0;
	int id[N];
	memset(tmp , 0 , sizeof(tmp));
	memset(id , 0 , sizeof(id));
	for(int i = 1 ; i <= n ; i++) {
		if(id[isl[i]] != 0)
			continue;
		id[isl[i]] = 1;
		tmp[++size] = islval[isl[i]];
	}
	std::sort(tmp + 1 , tmp + size + 1);

#if DEBUG
	for(int i = 1 ; i <= size ; i++)
		cout << tmp[i] << ' ';
	cout << '\n';
#endif

	int ans = 0 , cnt = 0;
	for(int i = size ; i > 0 ; --i) {
		++cnt;
		if(cnt > k)
			break;
		ans += tmp[i];
	}
	return ans;
}
int main() {
	freopen("azeroth.in" , "r" , stdin);
	freopen("azeroth.out" , "w" , stdout);
	
	n = read() , m = read();
	UF::init();
	for(int i = 1 ; i <= m ; i++) {
		int u = read() , v = read();
		if(u == v)	continue;

//		if(!check[hash(u , v)])
//			check[hash(u , v)] = check[hash(v , u)] = true , 
			addedge(u , v) , UF::uni(u , v);
	}
	check.clear();

	int sumval = 0;
	for(int i = 1 ; i <= n ; i++)
		val[i] = read();
	k = read() + 1;
	

	tj::rebuild();//缩点并重新建图

	topo();//DAG DP

	cout << GetAns() << '\n';
#if DEBUG
	for(int i = 1 ; i <= n ; i++) {
		cout << i << ' ' << isl[i] << ":\t";
		for(int j = head[i] ; j ; j = ed[j].nxt)
			cout << ed[j].to << '\t';
		cout << '\n';
	}
#endif
	return 0;
}