首页 > 代码库 > hihoCoder 1185 连通性·三（Tarjan缩点+暴力DFS）

hihoCoder 1185 连通性·三（Tarjan缩点+暴力DFS）

2024-08-27 22:51:04   219人阅读

#1185 : 连通性·三

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

暑假到了!!小Hi和小Ho为了体验生活，来到了住在大草原的约翰家。今天一大早，约翰因为有事要出去，就拜托小Hi和小Ho忙帮放牧。

约翰家一共有N个草场，每个草场有容量为W[i]的牧草，N个草场之间有M条单向的路径。

小Hi和小Ho需要将牛羊群赶到草场上，当他们吃完一个草场牧草后，继续前往其他草场。当没有可以到达的草场或是能够到达的草场都已经被吃光了之后，小hi和小Ho就把牛羊群赶回家。

一开始小Hi和小Ho在1号草场，在回家之前，牛羊群最多能吃掉多少牧草？

举个例子：

技术分享

图中每个点表示一个草场，上部分数字表示编号，下部分表示草场的牧草数量w。

在1吃完草之后，小Hi和小Ho可以选择把牛羊群赶到2或者3，假设小Hi和小Ho把牛羊群赶到2：

吃完草场2之后，只能到草场4，当4吃完后没有可以到达的草场，所以小Hi和小Ho就把牛羊群赶回家。

若选择从1到3，则可以到达5，6：

选择5的话，吃完之后只能直接回家。若选择6，还可以再通过6回到3，再到5。

所以该图可以选择的路线有3条：

1->2->4 		total: 111->3->5 		total: 91->3->6->3->5: 		total: 13

所以最多能够吃到的牧草数量为13。

 

 

本题改编自USACO月赛金组

提示：强连通分量

输入

第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000

第2行：N个正整数，第i个整数表示第i个牧场的草量w[i]。1≤w[i]≤100,000

第3..M+2行：2个正整数，u,v。表示存在一条从u到v的单向路径。1≤u,v≤N

输出

第1行：1个整数，最多能够吃到的牧草数量。

 

样例输入
6 62 4 3 5 4 41 22 41 33 53 66 3
样例输出
13

 

题目链接：hihoCoder 1185

tarjan缩点后重新建立DAG图，然后暴力DFS出最大的值。

代码：

#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair<int, int> pii;typedef long long LL;const double PI = acos(-1.0);const int N = 20010;const int M = 100010;struct edge{	int to, nxt;};edge E[M], rE[M];int head[N], rhead[N], tot, rtot;int dfn[N], low[N], st[N], ts, scc, top, belong[N], arr[N], block[N];bool ins[N];int ans;void init(){	CLR(head, -1);	CLR(rhead, -1);	tot = rtot = 0;	CLR(dfn, 0);	CLR(low, 0);	ts = scc = top = 0;	CLR(belong, 0);	CLR(block, 0);	CLR(ins, false);	ans = 0;}inline void add(int s, int t, edge e[], int h[], int &Tot){	e[Tot].to = t;	e[Tot].nxt = h[s];	h[s] = Tot++;}void Tarjan(int u, const int h[], const edge e[]){	dfn[u] = low[u] = ++ts;	st[top++] = u;	ins[u] = true;	int i, v;	for (i = h[u]; ~i; i = e[i].nxt)	{		v = e[i].to;		if (!dfn[v])		{			Tarjan(v, h, e);			low[u] = min(low[u], low[v]);		}		else if (ins[v])			low[u] = min(low[u], dfn[v]);	}	if (low[u] == dfn[u])	{		++scc;		do		{			v = st[--top];			belong[v] = scc;			ins[v] = false;		} while (u != v);	}}void dfs(int u, int sum){	sum += block[u];	if (sum > ans)		ans = sum;	for (int i = rhead[u]; ~i; i = rE[i].nxt)	{		int v = rE[i].to;		dfs(v, sum);	}}int main(void){	int n, m, a, b, i, j;	while (~scanf("%d%d", &n, &m))	{		init();		for (i = 1; i <= n; ++i)			scanf("%d", arr + i);		for (i = 0; i < m; ++i)		{			scanf("%d%d", &a, &b);			add(a, b, E, head, tot);		}		for (i = 1; i <= n; ++i)			if (!dfn[i])				Tarjan(i, head, E);		for (i = 1; i <= n; ++i)		{			block[belong[i]] += arr[i];			arr[i] = 0;		}		for (i = 1; i <= n; ++i)		{			for (j = head[i]; ~j; j = E[j].nxt)			{				b = E[j].to;				if (belong[i] != belong[b])				{					add(belong[i], belong[b], rE, rhead, rtot);				}			}		}		dfs(belong[1], 0);		printf("%d\n", ans);	}	return 0;}

hihoCoder 1185 连通性·三（Tarjan缩点+暴力DFS）


联系
我们