首页 > 代码库 > BZOJ 1179 Atm(强连通分量缩点+DP)
BZOJ 1179 Atm(强连通分量缩点+DP)
题目说可以通过一条边多次,且点权是非负的,所以如果走到图中的一个强连通分量,那么一定可以拿完这个强连通分量上的money。
所以缩点已经很明显了。缩完点之后图就是一个DAG,对于DAG可以用DP来求出到达每一个点的money最大值。具体实现我用的是bfs。
然后如果一个强连通分量内有酒馆,那么这个点就可以更新答案啦。
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi acos(-1.0) # define eps 1e-3 # define MOD 100000007 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { int res=0, flag=0; char ch; if((ch=getchar())==‘-‘) flag=1; else if(ch>=‘0‘&&ch<=‘9‘) res=ch-‘0‘; while((ch=getchar())>=‘0‘&&ch<=‘9‘) res=res*10+(ch-‘0‘); return flag?-res:res; } void Out(int a) { if(a<0) {putchar(‘-‘); a=-a;} if(a>=10) Out(a/10); putchar(a%10+‘0‘); } const int N=500005; //Code begin... struct Edge{int p, next;}edge[N], edge1[N]; int head[N], head1[N], cnt=1, cnt1=1, node[N], ans=0, dis[N]; int Low[N], DFN[N], Stack[N], Belong[N], Index, top, scc, num[N]; bool Instack[N], isjiu[N], jiu[N]; queue<int>Q; void add_edge(int u, int v){edge[cnt].p=v; edge[cnt].next=head[u]; head[u]=cnt++;} void add_edge1(int u, int v){edge1[cnt1].p=v; edge1[cnt1].next=head1[u]; head1[u]=cnt1++;} void Tarjan(int u) { int v; Low[u]=DFN[u]=++Index; Stack[top++]=u; Instack[u]=true; for (int i=head[u]; i; i=edge[i].next) { int v=edge[i].p; if (!DFN[v]) { Tarjan(v); if (Low[u]>Low[v]) Low[u]=Low[v]; } else if (Instack[v]&&Low[u]>DFN[v]) Low[u]=DFN[v]; } if (Low[u]==DFN[u]) { scc++; do{ v=Stack[--top]; Instack[v]=false; Belong[v]=scc; num[scc]+=node[v]; jiu[scc]|=isjiu[v]; }while (v!=u); } } void solve(int n){ mem(DFN,0); mem(Instack,0); mem(num,0); Index=scc=top=0; FOR(i,1,n) if (!DFN[i]) Tarjan(i); } int main () { int n, m, u, v, s, p; n=Scan(); m=Scan(); while (m--) u=Scan(), v=Scan(), add_edge(u,v); FOR(i,1,n) node[i]=Scan(); s=Scan(); p=Scan(); FOR(i,1,p) u=Scan(), isjiu[u]=1; solve(n); FO(i,1,n) for (u=head[i]; u; u=edge[u].next) { v=edge[u].p; if (Belong[v]==Belong[i]) continue; add_edge1(Belong[i],Belong[v]); } Q.push(Belong[s]); dis[Belong[s]]=num[Belong[s]]; while (!Q.empty()) { u=Q.front(); Q.pop(); if (jiu[u]) ans=max(ans,dis[u]); for (int i=head1[u]; i; i=edge1[i].next) { v=edge1[i].p; if (dis[v]>=dis[u]+num[v]) continue; dis[v]=dis[u]+num[v]; Q.push(v); } } printf("%d\n",ans); return 0; }
BZOJ 1179 Atm(强连通分量缩点+DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。