Description
Farmer John has a list of N (3 <= N <= 10,000) chores that must be completed. Each chore requires an integer time (1 <= length of time <= 100) to complete and there may be other chores that must be completed before this chore is started. We will call these
prerequisite chores. At least one chore has no prerequisite: the very first one, number 1. Farmer John's list of chores is nicely ordered, and chore K (K > 1) can have only chores 1,.K-1 as prerequisites. Write a program that reads a list of chores from 1
to N with associated times and all perquisite chores. Now calculate the shortest time it will take to complete all N chores. Of course, chores that do not depend on each other can be performed simultaneously.
Input
* Lines 2..N+1: N lines, each with several space-separated integers. Line 2 contains chore 1; line 3 contains chore 2, and so on. Each line contains the length of time to complete the chore, the number of the prerequisites, Pi, (0 <= Pi <= 100), and the Pi
prerequisites (range 1..N, of course).
Output
#include<stdio.h> #include<cstring> using namespace std; const long maxn=10001;const long INF=1; bool flag[maxn];long cnt,i,n,j,xx,time,y,h,t,go,now,ans,tong; long dis[maxn],begin[maxn],end[maxn],x[200*maxn]; struct arr{long l,r,s,next;}a[200*maxn]; void make_up(long l,long r,long v) { a[++cnt].l=l;a[cnt].r=r;a[cnt].s=-v;a[cnt].next=-1; if (begin[l]==0) {begin[l]=cnt;end[l]=cnt;} else {a[end[l]].next=cnt;end[l]=cnt;} } int main() { //freopen("chores.in","r",stdin);freopen("chores.out","w",stdout); scanf("%ld",&n); for (i=1;i<=n;i++) { scanf("%ld",&time); scanf("%ld",&xx); for (j=1;j<=xx;j++) { scanf("%ld",&y); make_up(y,i,time); } if (xx==0) make_up(0,i,time); } memset(flag,0,sizeof(flag));memset(dis,INF,sizeof(dis)); h=0;t=1;x[1]=0;dis[0]=0;flag[0]=true; while (h<t) { now=x[++h];if (begin[now]==0) continue;i=begin[now]; while (true) { go=a[i].r; if (dis[now]+a[i].s<dis[go]) { dis[go]=dis[now]+a[i].s; if (!flag[go]) { flag[go]=true; x[++t]=go; } } if (a[i].next==-1) break;i=a[i].next; } flag[now]=false; } for (i=1;i<=n;i++) if (-dis[i]>ans) ans=-dis[i]; printf("%ld",ans); //scanf("%ld",&n); return 0; }
然而交了之后一直TLE,自己下了个数据,发现最后一个点大概要13s左右!想不到在稠密图里,SPFA的效率又如此之低!(边表的常数又很大)无论怎么优化都不行!
#include<stdio.h> #include<cstring> using namespace std; long f[10001],n,i,j,max,ans,xx,y; int main() { //freopen("chores.in","r",stdin);freopen("chores.out","w",stdout); scanf("%ld",&n); for (i=1;i<=n;i++) { scanf("%ld",&f[i]); scanf("%ld",&xx);max=0; for (j=1;j<=xx;j++) { scanf("%ld",&y); if (f[y]>max) max=f[y]; } f[i]+=max; if (f[i]>ans) ans=f[i]; } printf("%ld",ans); //scanf("%ld",&n); return 0; }
然而仔细一想,我发现他们只是钻了一个数据的漏洞——刚好数据的前后关系是由小到大的。思考了很长时间,我研究出了一个更加高级的算法——记忆化深搜+边表优化!
#include<stdio.h> #include<cstring> using namespace std; const long maxn=10001;const long INF=1; long time[maxn],dp[maxn],begin[maxn],end[maxn],cnt,j,n,i,x,y,ans; struct arr{long l,r,next;}a[200*maxn]; void make_up(long l,long r) { a[++cnt].l=l;a[cnt].r=r;a[cnt].next=-1; if (begin[l]==0) {begin[l]=cnt;end[l]=cnt;} else {a[end[l]].next=cnt;end[l]=cnt;} } long go(long k) { if (dp[k]>0) return dp[k]; long now=begin[k]; while (now>0) { long temp=go(a[now].r); dp[k]=(temp>dp[k])?temp:dp[k]; now=a[now].next; } dp[k]+=time[k]; return dp[k]; } int main() { //freopen("chores.in","r",stdin);freopen("chores.out","w",stdout); scanf("%ld",&n); for (i=1;i<=n;i++) { scanf("%ld",&time[i]); scanf("%ld",&x); for (j=1;j<=x;j++) { scanf("%ld",&y);make_up(i,y); } if (x==0) dp[i]=time[i]; } for (i=1;i<=n;i++) { long temp=go(i); ans=(temp>ans)?temp:ans; } printf("%ld",ans); //scanf("%ld",&n); return 0; }
希望众神牛看到后能够留言指导!