并查集的题。一开始的时候没看懂题,以为要用最短路算法去做,结果样例都没过,后在队友的指导下终于理解了题意。用并查集写好后,第一次提交莫名奇妙的RE,检查后发现查函数没写返回值(编译器没提示呢?而且样例也过了),第二次提交是WA,经检查后发现是无穷大设得不够大。下次一定要注意这些细节问题。
#include <stdio.h> #define N 10005 #define INF 0x7fffffff int p[N],d[N],out[N],n; void make_set() { int i; for(i=0;i<=n;i++) p[i]=i,d[i]=0,out[i]=0; } int find_set(int i) { int pi=p[i]; if(i!=p[i]) p[i]=find_set(p[i]); if(pi!=p[i]) d[i]+=d[pi]; return p[i]; } void union_set(int i,int j,int x) { int pi=find_set(i),pj=find_set(j); p[pj]=pi; d[pj]=d[i]-d[j]+x; } int main() { int t1,t2,i,u,l,k,a,b,min,max,ans1,ans2; while(~scanf("%d%d%d",&n,&t1,&t2)) { make_set(); for(i=1;i<=n;i++) { scanf("%d%d%d",&u,&l,&k); out[u]++; while(k--) { scanf("%d%d",&a,&b); l-=b-a; } union_set(u,i,l*t1+t2); } min=INF,max=0; for(i=0;i<=n;i++) { find_set(i); if(out[i]==0&&d[i]<min) min=d[i],ans1=i; if(out[i]==0&&d[i]>max) max=d[i],ans2=i; } printf("%d %d\n",ans1,ans2); } return 0; }