解析
这道题比较水。
求最快什么时候做完作业?
如果要最快完成第i份作业,那么是i的前继那些作业都要完成之后才能够完成i,所以,为了尽快完成i,我们要把i的前继的作业全部先做完。
最慢什么时候做完作业?
也就是说再不完成i的前提下,我最多能够做多少作业。那哪些作业是不可以做呢?其实就是它的后继。
那么你先正着做一次 (DFS),再反一次做 (DFS) 就可以了。
(Code)
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 20005;
int n , m , t[N] , vis[N] , h[N] , hh[N] , tot , tott;
struct edge{
int to , nxt;
}e[N] , ee[N];
inline void adde(int x , int y)
{
e[++tot] = (edge){y , h[x]};
h[x] = tot;
}
inline void addee(int x , int y)
{
ee[++tott] = (edge){y , hh[x]};
hh[x] = tott;
}
inline void dfs1(int x)
{
vis[x] = 1;
for(register int i = hh[x]; i; i = ee[i].nxt)
{
int v = ee[i].to;
if (vis[v]) continue;
dfs1(v);
}
}
inline void dfs2(int x)
{
vis[x] = 1;
for(register int i = h[x]; i; i = e[i].nxt)
{
int v = e[i].to;
if (vis[v]) continue;
dfs2(v);
}
}
int main()
{
scanf("%d%d" , &n , &m);
int sum = 0;
for(register int i = 1; i <= n; i++) scanf("%d" , &t[i]) , sum += t[i];
int u , v;
for(register int i = 1; i <= m; i++)
{
scanf("%d%d" , &u , &v);
adde(u , v) , addee(v , u);
}
for(register int i = 1; i <= n; i++)
{
int er = 0 , la = 0;
memset(vis , 0 , sizeof vis);
dfs1(i);
for(register int i = 1; i <= n; i++) if (vis[i]) er += t[i];
memset(vis , 0 , sizeof vis);
dfs2(i);
for(register int i = 1; i <= n; i++) if (vis[i]) la += t[i];
printf("%d %d
" , er , sum - la + t[i]);
}
}