首页 > 其他分享 >缩点后 spfa求最长路(不知道为什么top+dp做不了)

缩点后 spfa求最长路(不知道为什么top+dp做不了)

时间:2022-09-01 23:56:30浏览次数:50  
标签:缩点 int top spfa include dp

#include<queue>
#include<cstdio>
#include<cstring>
#define N 500005
using namespace std;
struct edge{
    int to,val,next;
} e[N];
int m,n,p,s,cnt,g[N],u[N],v[N],w[N],hd[N],bar[N],dis[N],dfn[N],low[N],stk[N],sum[N];
bool vis[N];
queue <int> q;
int ans=0,top=0,tot=0,total=0;
 inline int min(int a,int b)
  {return a<b?a:b;}
 void add(int u,int v)
 {
 	cnt++;
 	e[cnt].to=v;
 	e[cnt].next=hd[u];
 	hd[u]=cnt;
 }
 void build(int u,int v,int w)
 {
 	cnt++;
 	e[cnt].to=v;
 	e[cnt].val=w;
 	e[cnt].next=hd[u];
 	hd[u]=cnt;
 }
 void clear()
 {
 	cnt=0;
 	memset(e,0,sizeof(e));
 	memset(hd,0,sizeof(hd));
 }
 void readln()
 {
 	clear();
 	scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        add(u[i],v[i]);
    }
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    scanf("%d%d",&s,&p);
    for(int i=1;i<=p;i++) scanf("%d",&bar[i]);
 }
 void Tarjan(int x)
 {
 	dfn[x]=low[x]=++total;
 	stk[++top]=x;vis[x]=true;
 	for(int i=hd[x];i;i=e[i].next)
 	{
 		int t=e[i].to;
 		if(!dfn[t])
 		{
 			Tarjan(t);
 			low[x]=min(low[x],low[t]);
 		}
 		else if(vis[t])
 		 low[x]=min(low[x],dfn[t]);
 	}
 	if(dfn[x]==low[x])
 	{
 		tot++;
 		do{
 			int tp=stk[top];
 			sum[tot]+=w[tp];
 			vis[tp]=false;
 			g[tp]=tot;
 		}while(stk[top--]!=x);
 	}
 }
 void Spfa(int s)
 {
 	for(int i=1;i<=tot;i++) dis[i]=0;
 	int gs=g[s];
    q.push(gs);
 	vis[gs]=true;
 	dis[gs]=sum[gs];
 	while(!q.empty())
 	{
 		int h=q.front();q.pop();
 		vis[h]=false;
 		for(int i=hd[h];i;i=e[i].next)
 		{
 			int t=e[i].to;
 			if(dis[t]<dis[h]+e[i].val)
 			{
 				dis[t]=dis[h]+e[i].val;
 				if(!vis[t])
 				{
 					q.push(t);
 					vis[t]=true;
 				}
 			}
 		}
 	}
 }
int main()
{
    readln();
    for(int i=1;i<=n;i++)
     if(!dfn[i]) Tarjan(i);
    clear();
    for(int i=1;i<=m;i++)
     if(g[u[i]]!=g[v[i]])
      build(g[u[i]],g[v[i]],sum[g[v[i]]]);
    Spfa(s);
    for(int i=1;i<=p;i++)
     ans=max(ans,dis[g[bar[i]]]);
    printf("%d",ans);
    return 0;
}

标签:缩点,int,top,spfa,include,dp
From: https://www.cnblogs.com/liang302/p/16648254.html

相关文章

  • Redis 管理工具 - Redis Desktop Manager
     RedisDesktopManager可以轻松管理Redis桌面。为您提供了一个易于使用的GUI,可以访问您的Redis数据库并执行一些基本操作:将键视为树,CRUD键,通过shell执行命令。RESP.app......
  • iZotope RX 10专业音频修复软件
    iZotope RXforMac是一款好用专业的音频修复软件。iZotopeRX专为满足后期制作专业人士的苛刻需求而设计,引入了全新的机器学习处理功能,强大的AudioSuite工具以及高达7.1......
  • linux top 学习及详解 top变红
    linuxtop学习及详解top变红-豌豆ip代理 https://www.wandouip.com/t5i258522/众所周知,linux的top命令是服务器工程师和运维最常用的工具之一,类似于windows的任务管......
  • spfa
    #include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10,INF=0x3f3f3f3f;intn,m,dis[N],h[N],idx;boolvis[N];structedge{intn,t,l......
  • 爬某豆瓣读书 Top 250
    importreimporttimeimportrequestsfromlxmlimportetree#爬某豆瓣读书Top250#浏览器的代理#在网址上输入about://version浏览器的代理cz={'User-Agent':......
  • 【debug】 Linux中top的使用
    在我们日常的开发中,我们经常需要查看每个线程的cpu使用情况。其实,在linux中,top也是我们查看cpu使用状况的一个好帮手top:先查看每一个进程的使用状况我们可以发现PID:38......
  • stopPropagation, preventDefault 和 return false 的区别
    stopPropagation阻止事件的冒泡和捕获。因为事件可以在各层级的节点中传递,不管是冒泡还是捕获,有时我们希望事件在特定节点执行完之后不再传递,可以使用事件对象的s......
  • 拓扑排序(topsort)
    给定一个n个点m条边的有向图,点的编号是1到n,图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出−1。若一个由图中所有点构成......
  • 国产浏览器中的Top1
    随着不同产品的涌出,满足了用户的各种需求,也使产品的可替代性提高了,我们针对用户的需求设计了一款超前的浏览器,星海浏览器是一款针对年轻人群体,能够无障碍访问全球站点的便......
  • 解析OCC几何体(TopoDS_Shape)生成自定义off文件(转)
    voidParseTopoDSShapeToOff(constTopoDS_Shape&aShape){//0计算顶点和顶点索引//std::vector<osg::Vec3d>vertexArray;BRepMesh_IncrementalMesh(aSh......