Description
Input
Output
输出n行。第i行输出两个整数，分别表示第i份作业最早完成的时刻以及最晚完成的时刻，两个整数之间以一个空格间隔。
Sample Input
4 43 4 5 61 21 32 43 4
Sample Output
3 37 128 1218 18
Data Constraint
对于30%的数据，n<=100，m<=5000
对于100%的数据，1<=n<=2000,0<=m<=10000,1<=timei<=1000000,1<=ai,bi<=n。
Solution
最早的时间即为前面所有有关系的点都做完了，dfs搜一遍标记上，加入答案。
最晚的时间即为只有后面有关系的所有点没有做完，dfs搜一遍标记上，用总时间减去。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define N 2005
using namespace std;
I n,m,a[N],x,y,bz[N];
ll f[N],g[N],sum;
I t[N*5],nx[N*5],ls[N],tot;
I t2[N*5],nx2[N*5],ls2[N],tot2;
void add(I x,I y){t[++tot]=y,nx[tot]=ls[x],ls[x]=tot;}
void add2(I x,I y){t2[++tot2]=y,nx2[tot2]=ls2[x],ls2[x]=tot2;}
void dg(I x,I rt,I p){bz[x]=1;if(p) f[rt]+=a[x];else g[rt]+=a[x];for(I k=p?ls[x]:ls2[x];k;k=p?nx[k]:nx2[k]){I son=p?t[k]:t2[k];if(!bz[son]) dg(son,rt,p);}
}
I main(){freopen("homework.in","r",stdin);freopen("homework.out","w",stdout);scanf("%d%d",&n,&m);F(i,1,n) scanf("%d",&a[i]),sum+=a[i];while(m--){scanf("%d%d",&x,&y);add2(x,y),add(y,x);}F(i,1,n){memset(bz,0,sizeof bz);dg(i,i,1);memset(bz,0,sizeof bz);dg(i,i,0);}F(i,1,n) printf("%lld %lld\n",f[i],sum-g[i]+a[i]);return 0;
}