Back to Posts

BZOJ1179[APIO]Atm

Posted in 题解

题目链接

题目大意

给定一个n个点,m条边有向有环的图,然后每一个点都有一个权值。给定p个可当结束点的点p≤n,和一个起点S,求出一条路径,使得结束点在p个点之中,且经过点的权值和最大,输出这个最大值。

Input

第一行包含两个整数N、M。N表示路口的个数,M表示道路条数。

接下来M行,每行两个整数,这两个整数都在1到N之间,

第i+1行的两个整数表示第i条道路的起点和终点的路口编号。

接下来N行,每行一个整数,按顺序表示每个路口处的ATM机中的钱数。

接下来一行包含两个整数S、P,S表示市中心的编号,也就是出发的路口。P表示酒吧数目。

接下来的一行中有P个整数,表示P个有酒吧的路口的编号

N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。

输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。

Output

输出一个整数,表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

Sample Input

6 7

1 2

2 3

3 5

2 4

4 1

2 6

6 5

10

12

8

16

1 5

1 4

4

3

5

6

Sample Output

47

HINT

n=m≤500000

题解:

水题+1.

其实我也不会证明我算法的复杂度的正确性

首先,求最大值,我的反应时DAG上的DP。

看到是一个有向图,然后一个点还可以经过多次,那就只能说明这个图中存在环,然后你考虑对

于任意的一个环,我们都可以从其中的任意一个点进入,任意一个点走出,再加上收益非负,所以环上的所有收益都是可以得到的。

所以tarjan缩点,将环上的所有点的收益加到这个环缩成的点上,然后所有的环外边都连到这个点上。

然后他就成了一个DAG,然后就DP就行了,类似SPFA那样的DP。

然后我开觉得可以卡掉这种做法,卡成O(mn)的复杂度,然后抱着TLE的心态码码码……

然后过了,可能数据水吧,所以开头说不会证明复杂度,恳请路过dalao解释一下

我个人感觉看出算法的题眼:

1、一个点可以经过多次。

2、收益非负(如果有负的就不能走环上的所有点了)。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define MAXN 600010

using namespace std;

int head[MAXN],stack[MAXN],col[MAXN];
int dfn[MAXN],low[MAXN],vis[MAXN],c[MAXN],ed[MAXN];
int num,cnt,col_num,S,P,n,m;
long long tot;
long long f[MAXN],val[MAXN];

struct po{
	int nxt,to;
}a[MAXN];
struct edge{
	int from,to;
}e[MAXN];

void add(int from,int too){a[++num].nxt=head[from];a[num].to=too;head[from]=num;}

void tarjan(int x)
{
	vis[x]=1;stack[++cnt]=x;
	dfn[x]=low[x]=++tot;
	for(int i=head[x];i;i=a[i].nxt)
	{
		int y=a[i].to;
		if(vis[y]) low[x]=min(low[x],dfn[y]);
		else if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
	}
	if(dfn[x]==low[x])
	{
		++col_num;
		while(stack[cnt]!=x)
		{
			int u=stack[cnt--];
			col[u]=col_num;vis[u]=0;
			val[col_num]+=c[u];
		}
		cnt--;col[x]=col_num;vis[x]=0;
		val[col_num]+=c[x];
	}
}

void clear()
{
	for(int i=1;i<=n;i++) head[i]=0;
	num=0;
}

void rebuild()
{
	for(int i=1;i<=m;i++)
	{
		int u=e[i].from,v=e[i].to;
		if(col[u]!=col[v]) add(col[u],col[v]);
	}
}

queue<int>q;

void DP()
{
	int s=col[S];
	q.push(s);vis[s]=1;f[s]=val[s];
	while(!q.empty())
	{
		int x=q.front();q.pop();vis[x]=0;
		for(int i=head[x];i;i=a[i].nxt)
		{
			int y=a[i].to;
			if(f[y]<f[x]+val[y])
			{
				f[y]=f[x]+val[y];
				if(!vis[y])
				{
					q.push(y);
					vis[y]=1;
				}
			}
		}
	}
}

void output()
{
	long long ans=0;
	for(int i=1;i<=P;i++) ans=max(ans,f[col[ed[i]]]);
	printf("%lld",ans);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		scanf("%d%d",&e[i].from,&e[i].to);
		add(e[i].from,e[i].to);
	}
	
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	scanf("%d%d",&S,&P);
	for(int i=1;i<=P;i++) scanf("%d",&ed[i]);
	
	for(int i=1;i<=n;i++)
	if(!col[i]) tarjan(i);	
	
	clear();
	rebuild();
	DP();
	output();
	
	return 0;
}
/*
6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1 5
1 4
4
3
5
6
*/

开始把时间标和栈头变量写错了,结果RE了一次(还好及时发现)。

刷水题真开心

总结:

1、我好像以前都懒得写DAG上的DP,就拿这个水题补锅了。

2、注意权值是否非负,别看见环就缩,不是所有的题都能像这个题这样搞的。

3、巧用Tarjan+板子打熟

4、犯的几个小错:变量写混了+输入数据打错了

——By GaryStack

Read Next

literacy class