题:https://www.cometoj.com/problem/0461

分析:求边双,最后求多汇点最长路

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#define pb push_back
using namespace std;
const int M=5e5+;
int sum[M],book[M],jiu[M],head[M],dfn[M],low[M],vis[M],sta[M],cmp[M],dis[M],val[M],newval[M],tot,top,cnt,num;
vector<int>g[M];
struct node{
int v,w,nextt;
}e[M];
void tarjan(int u,int f){
dfn[u]=low[u]=++cnt;
sta[++top]=u;
vis[u]=;
for(int i=;i<g[u].size();i++){
int v=g[u][i];
if(v==f)
continue;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
cmp[u]=++tot;
int countt=val[u];
vis[u]=;
int len=top;
while(sta[top]!=u){
countt+=val[sta[top]];
cmp[sta[top]]=tot;
vis[sta[top--]]=;
}
top--;
sum[tot]=len-top;
newval[tot]=countt;
}
}
void addedge(int u,int v,int w){
e[num].v=v;
e[num].w=w;
e[num].nextt=head[u];
head[u]=num++;
}
int spfa(int s,int t){
for(int i=s;i<=t;i++)
dis[i]=,vis[i]=;
queue<int>que;
que.push(s);
while(!que.empty()){
int u=que.front();
que.pop();
vis[u]=;
for(int i=head[u];~i;i=e[i].nextt){
int v=e[i].v;
if(dis[v]<dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!vis[v])
vis[v]=,que.push(v); }
}
}
return dis[t];
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
head[i]=-;
for(int i=,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
g[u].pb(v);
}
for(int i=;i<=n;i++)
scanf("%d",&val[i]);
int s,p;
scanf("%d%d",&s,&p);
for(int i=;i<=p;i++)
scanf("%d",&jiu[i]);
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i,-);
s=cmp[s];
int t=tot+;
for(int i=;i<=n;i++)
for(int j=,v;j<g[i].size();j++){
v=g[i][j];
if(cmp[i]!=cmp[v]){
//m cout<<cmp[i]<<"!!!!!"<<cmp[v]<<"!!!!"<<newval[cmp[i]]<<endl;
addedge(cmp[i],cmp[v],newval[cmp[i]]);
}
}
for(int i=;i<=p;i++){
if(book[cmp[jiu[i]]]==)
continue;
book[cmp[jiu[i]]]=;
int w=newval[cmp[jiu[i]]];
// if(sum[cmp[jiu[i]]]>1)
// w=0;
// cout<<cmp[jiu[i]]<<"!!!!!"<<t<<"!!!!"<<w<<endl;
addedge(cmp[jiu[i]],t,w);
}
printf("%d\n",spfa(s,t));
}

最新文章

  1. 渗透测试-信息收集-c段收集
  2. linux 查看php-fpm 进程数
  3. mongo(删除操作)
  4. 实现自己的js框架
  5. eclipse导入git项目(转)
  6. Leetcode#61 Rotate List
  7. Javascript线程及定时机制
  8. 从零开始学Axure原型设计(进阶篇)
  9. 【转】int &amp;&amp; 非常量右值
  10. HDU-2077-汉诺塔IV
  11. shell入门笔记1:执行方式、运行方式、变量、替换
  12. zabbix监控Elasticsearch集群
  13. 二.GC相关之Java内存模型
  14. eclipse版本选择
  15. FFmpeg 学习(七):FFmpeg 学习整理总结
  16. Reading List on Automated Program Repair
  17. 浅析软件工程中的UML建模技术
  18. NESTED内部事务异常会回滚 外部事务不会回滚 ;内部事务没有异常,外部事务有异常 则整体事务都回滚
  19. contentInsetAdjustmentBehavior各个值之间的区别
  20. scroll事件的优化以及scrollTop的兼容性

热门文章

  1. part6 城市页面搜索内容开发
  2. POJ - 3665 iCow(模拟)
  3. jQuery.ajax提交JSON数据
  4. offsetof宏与container_of宏
  5. DRF框架之DRF的引入
  6. 设计模式讲解3:ChainOfResponsibility模式源码
  7. 干货 | 京东技术中台的Flutter实践之路
  8. LeetCode No.166,167,168
  9. ansible-playbook权限提升多种方式
  10. CommandNotFoundError: No command &#39;conda conda&#39;.