一开始 自己写了个记忆化搜索的代码 结果总是 RE 检查了n遍 数组也没开小 估计是 爆栈了 于是我把代码改成了非递归形式的
代码里还用到了队列写着写着发现我写的和spfa的思路是一样的嘛 不过还是超时了 又检查了n遍发现 我把结束的条件看错了 = = |||
好吧 再改
改完后还是wa ！！！
啊~~妹的
又是 一阵检查 原来 他讲的是绝对值> 0 （>o<）因为就是讲有复值的情况 真的 烦躁了
好吧 我再改。。。
还好 这次 改完a了 不然真的要崩溃了。。。。。
本来 一道水题 搞了这么久 每次都是这样。。
贴一下 RE的代码
题意 n个点m条有向边，每个点有一个权值v[i]，求一条从入度为0的点到出度为0的点路径上的经过所有点权值之和最大值
#include<iostream> #include<string.h> #include<stdio.h> #define INF 1000000000 using namespace std; struct E {int to;int next;}edge[2000002]; int w[100012],adj[100012],num,in0[100012]; long long d[100012]; void add(int a,int b) { edge[num].to =b; edge[num].next =adj[a]; adj[a]=num++; } long long dp(int s) { if(adj[s]==-1) return d[s]=w[s]; if(d[s]) return d[s]; long long maxx=-1*INF; for(int i=adj[s];i!=-1;i=edge[i].next) { int v=edge[i].to ; if(maxx<dp(v)) maxx=d[v]; } return d[s]=maxx+w[s]; } int main() { int i,j,n,m,a,b; while(scanf("%d",&n)) { if(n==0) break; scanf("%d",&m); for(i=1;i<=n;i++) scanf("%d",&w[i]); memset(adj,-1,sizeof(adj)); memset(in0,0,sizeof(in0)); memset(d,0,sizeof(d)); num=0; while(m--) { scanf("%d%d",&a,&b); add(a,b); in0[b]=1; //rudu buwei 0 } long long max1=-1*INF; for(i=1;i<=n;i++) if(in0[i]==0&&dp(i)>max1) max1=d[i]; printf("%lld ",max1); } return 0; }
这是 ac的
#include<iostream> #include<string.h> #include<stdio.h> #include<queue> #define INF 1000000000 using namespace std; struct E {int to;int next;}edge[2000002]; int w[100012],adj[100012],num,in0[100012],vis[100002]; queue<int > q; long long d[100012]; void add(int a,int b) { edge[num].to =b; edge[num].next =adj[a]; adj[a]=num++; } int main() { int i,j,n,m,a,b,t,v; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&w[i]); memset(adj,-1,sizeof(adj)); memset(in0,0,sizeof(in0)); for(i=1;i<=n;i++) d[i]=-1*INF; num=0; while(m--) { scanf("%d%d",&a,&b); add(b,a); in0[a]=1; //rudu buwei 0 } memset(vis,0,sizeof(vis)); long long max1=-1*INF; for(i=1;i<=n;i++) if(in0[i]==0) { q.push (i); d[i]=w[i]; vis[i]=1; } while(!q.empty ()) { t=q.front ();q.pop ();vis[t]=0; for(i=adj[t];i!=-1;i=edge[i].next ) { v=edge[i].to ; if(d[v]<d[t]+w[v]) { d[v]=d[t]+w[v]; if(!vis[v]) { q.push (v); vis[v]=1; } } } } long long maxx=-1*INF; for(i=1;i<=n;i++) { //printf("i %d %d ",i,d[i]); if(adj[i]==-1&&maxx<d[i]) maxx=d[i]; } printf("%lld ",maxx); } return 0; }