tarjan求调 60 pts
查看原帖
tarjan求调 60 pts
519384
Link_Cut_Y楼主2022/2/27 19:11
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 8e4 + 2e5 + 10;

int dfn[N], low[N], timestamp;
int stk[N], top, cnt;
bool in_stk[N];
int w[N], id[N], val[N];
int h[N], e[N << 1], ne[N << 1], idx;
int from[N], to[N];
int n, m;
int start, f[N], sz[N];
double renew[N];

void add(int a, int b)
{
	e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void tarjan(int u)
{
	dfn[u] = low[u] = ++ timestamp;
	stk[ ++ top] = u, in_stk[u] = true;
	
	for (int i = h[u]; i; i = ne[i])
	{
		int j = e[i];
		if (!dfn[j]) tarjan(j), low[u] = min(low[u], low[j]);
		else if (in_stk[j]) low[u] = min(low[u], low[j]);
	}
	
	if (low[u] == dfn[u])
	{
		++ cnt;
		int y;
		do 
		{
			y = stk[top -- ];
			in_stk[y] = false;
			id[y] = cnt;
			sz[cnt] ++ ;
			int x = w[y];
			while (x)
			{
				val[cnt] += x;
				x = (int)(x * renew[y]);
			}
		} while (y != u);
		
		if (sz[cnt] == 1) val[cnt] = w[y]; 
	}
}

void dfs(int u)
{
	if (f[u]) return;
	f[u] = val[u];
	
	int sum = 0;
	for (int i = h[u]; i; i = ne[i])
	{
		int j = e[i];
		dfs(j);
		sum = max(sum, f[j]);
	}
	
	f[u] += sum;
}

/*
void output()
{
	printf("强联通分量的个数为:%d\n", cnt);
	printf("每个强联通的权值:");
	for (int i = 1; i <= cnt; i ++ ) printf("%d ", val[i]);
	cout << endl;
	
	printf("每个强联通的大小:");
	for (int i = 1; i <= cnt; i ++ ) printf("%d ", sz[i]);
	cout << endl;
	
	printf("起点所在强联通分量的编号为:%d\n", id[start]);
	
	printf("每个节点所处编号是:\n");
	for (int i = 1; i <= n + m; i ++ ) cout << i << ' ' << id[i] << endl;
	cout << endl;
}
*/

int main()
{
	freopen("mushroom.in", "r", stdin);
	freopen("mushroom.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	
	for (int i = 1; i <= m; i ++ )
		scanf("%d%d%d%lf", &from[i], &to[i], &w[n + i], &renew[n + i]), add(from[i], n + i), add(n + i, to[i]);
	
	scanf("%d", &start);
	
	for (int i = 1; i <= n + m; i ++ )
		if (!dfn[i])
			tarjan(i);
	/*
	output();
	*/
	
	memset(h, 0, sizeof h);
	memset(e, 0, sizeof e);
	memset(ne, 0, sizeof ne);
	idx = 0;
	
	for (int i = 1; i <= m; i ++ )
	{
		if (id[from[i]] != id[n + i]) add(id[from[i]], id[n + i]);
		if (id[n + i] != id[to[i]]) add(id[n + i], id[to[i]]);
	}
	
	/*
	for (int i = 1; i <= cnt; i ++ )
	{
		printf("第%d个强联通分量的出边有:", i);
		for (int j = h[i]; j; j = ne[j])
		{
			int k = e[j];
			cout << k << ' ';
		}
		cout << endl;
	}
	*/
	
	dfs(id[start]);
	
	cout << f[id[start]] << endl;
	
	return 0;
}
2022/2/27 19:11
加载中...