【题目大意】

给出一张有点权的有向图,已知起点和可以作为终点的一些点,问由起点出发,每条边和每个点可以经过任意多次,经过点的权值总和最大为多少。

【思路】

由于可以走任意多次,显然强连通分量可以缩点。然后就是一张DAG图,跑SPFA最长路就好了。

听说Dijkstra写最长路会发生一些奇特的化学反应并且炸掉,还没想清楚姑且笔记一下。

 #include<bits/stdc++.h>
using namespace std;
const int MAXN=+;
struct edge
{
int to,len;
};
int n,m,s,p,money[MAXN],bar[MAXN],u[MAXN],v[MAXN];
vector<int> E[MAXN];
vector<edge> rE[MAXN];
stack<int> S;
queue<int> que;
int instack[MAXN],low[MAXN],dfn[MAXN],sum[MAXN],col[MAXN],cnt,tot;
int dis[MAXN],inque[MAXN]; void addedge(int u,int v)
{
E[u].push_back(v);
} void addedge2(int u,int v,int w)
{
rE[u].push_back((edge){v,w});
} void tarjan(int x)
{
dfn[x]=low[x]=++cnt;
instack[x]=;
S.push(x);
for (int i=;i<E[x].size();i++)
{
int to=E[x][i];
if (!instack[to])
{
tarjan(to);
low[x]=min(low[x],low[to]);
}
else if (instack[to]==)
{
low[x]=min(low[x],dfn[to]);
}
} if (dfn[x]==low[x])
{
tot++;
int tmp;
do
{
tmp=S.top();S.pop();
sum[tot]+=money[tmp];
col[tmp]=tot;
instack[tmp]=;
}while (tmp!=x);
}
} void spfa(int start)
{
memset(inque,,sizeof(inque));
for (int i=;i<=tot;i++) dis[i]=;
dis[start]=sum[start];
inque[start]=;
que.push(start);
while (!que.empty())
{
int head=que.front();que.pop();
inque[head]=;
for (int i=;i<rE[head].size();i++)
{
int to=rE[head][i].to,len=rE[head][i].len;
if (dis[to]<dis[head]+len)
{
dis[to]=dis[head]+len;
if (!inque[to])
{
inque[to]=;
que.push(to);
}
}
}
}
} void rebuild()
{
for (int i=;i<=m;i++)
if (col[u[i]]!=col[v[i]]) addedge2(col[u[i]],col[v[i]],sum[col[v[i]]]);
} void init()
{
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);
addedge(u[i],v[i]);
}
for (int i=;i<=n;i++) scanf("%d",&money[i]);
memset(bar,,sizeof(bar));
scanf("%d%d",&s,&p);
for (int i=;i<=p;i++)
{
int nowp;
scanf("%d",&nowp);
bar[nowp]=;
}
} void solve()
{
cnt=tot=;
memset(instack,,sizeof(instack));
for (int i=;i<=n;i++)
if (!instack[i]) tarjan(i);
rebuild();
spfa(col[s]);
int ans=-;
for (int i=;i<=n;i++)
if (bar[i]) ans=max(ans,dis[col[i]]);
printf("%d",ans);
} int main()
{
init();
solve();
return ;
}

最新文章

  1. [C#][算法] 用菜鸟的思维学习算法 -- 马桶排序、冒泡排序和快速排序
  2. job console部署
  3. 前端模板之EasyUI常用控件及参数
  4. Struts2之Struts2-2.5.5 Interceptor
  5. A cost-effective recommender system for taxi drivers
  6. PIC32MZ tutorial -- Input Capture
  7. ASP.NET 去除所有HTML标记的方法
  8. 一次 php nusoap 调试过程
  9. iptables 下开放ftp
  10. 591 - Box of Bricks
  11. jQuery插件实现的方法和原理简单说明
  12. 一个还算简单的微信消息SDK(基于.Net Standard 2.0)
  13. jenkins~集群分发功能和职责处理
  14. java 单例模式-饿懒汉模式
  15. codefroces 55D Beautiful numbers
  16. git cmd 命令在已有的仓库重新添加新的文件夹
  17. notepad++64位添加plugin manager
  18. WINDOWS中, 如何查看一个运行中的程序是64位还是32位的
  19. go语言net包udp socket的使用
  20. codeforces 235 div2 A. Vanya and Cards

热门文章

  1. Dubbo学习笔记7:Dubbo的集群容错与负载均衡策略
  2. elasticsearch-dump 迁移es数据 (elasticdump)
  3. ASP.NET MVC学习(二)之控制器Controller
  4. 基础知识点 关于 prototype __proto__
  5. laravel一个页面两个表格分页处理
  6. HTTP1.0 HTTP 1.1 HTTP 2.0主要区别
  7. yii2框架目录
  8. word技巧
  9. networkManger介绍
  10. oracle 建用户