最长路是NP呀
by hutao @ 2017-05-26 07:00:27
@[hutao](/space/show?uid=33365) dalao能不能详细说下。。。我搜不到。。。或者贴个链接也行啊。。。谢惹。。。
by 减维 @ 2017-05-26 17:53:25
最长路是NP复杂度 @[减维](/space/show?uid=35870)
by hutao @ 2017-05-26 18:17:26
所以不能用
by hutao @ 2017-05-26 18:17:48
@[hutao](/space/show?uid=33365) 谢谢大佬
by 减维 @ 2017-05-28 20:05:18
@[减维](/space/show?uid=35870) 不谢
by hutao @ 2017-05-28 20:11:55
其实可以用最长路做的
by heheabc @ 2017-06-13 19:22:56
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,l,r,c,cnt,hd,tl,q[1000005],dis[100005],vet[200005],head[100005],value[200005],Next[200005];
bool vis[100005];
void add(int a,int b,int c)
{
vet[++cnt]=b;
value[cnt]=c;
Next[cnt]=head[a];
head[a]=cnt;
}
void spfa(int st)
{
for (int i=0; i<=n; i++)
dis[i]=-1;
hd=0; tl=1;
dis[st]=0;
vis[st]=true;
q[0]=st;
while (hd!=tl)
{
int u=q[hd];
hd++;
if (hd==1000000) hd=0;
vis[u]=false;
for (int i=head[u]; i!=-1; i=Next[i])
{
int v=vet[i];
if (dis[v]<dis[u]+value[i])
{
dis[v]=dis[u]+value[i];
if (!vis[v])
{
vis[v]=true;
q[tl++]=v;
if (tl==1000000) tl=0;
}
}
}
}
}
int main()
{
scanf("%d",&n);
scanf("%d",&m);
memset(head,-1,sizeof(head));
for (int i=1; i<=n; i++)
{
add(i-1,i,0);
add(i,i-1,-1);
}
for (int i=1; i<=m; i++)
{
scanf("%d%d%d",&l,&r,&c);
add(l-1,r,c);
}
for (int i=n; i>=0; i--)
add(n+1,i,0);
spfa(n+1);
printf("%d\n",dis[n]);
return 0;
}
```
by heheabc @ 2017-06-13 19:23:16
@[heheabc](/space/show?uid=31172) 感觉写的差不多。。。然而死活不对。。。
by 减维 @ 2017-06-14 23:10:15
@[减维](/space/show?uid=35870) 最长路和最短路有区别吗...
by Cekavis @ 2017-07-07 16:50:19