【GDKOI2014】JZOJ2020年8月13日提高组T3 壕壕的寒假作业

【GDKOI2014】JZOJ2020年8月13日提高组T3 壕壕的寒假作业

题目

Description

Input

Output

输出n行。第i行输出两个整数，分别表示第i份作业最早完成的时刻以及最晚完成的时刻，两个整数之间以一个空格间隔。

Sample Input

4 4
3 4 5 6
1 2
1 3
2 4
3 4

Sample Output

3 3
7 12
8 12
18 18

Data Constraint

对于30%的数据，n<=100，m<=5000
对于100%的数据，1<=n<=2000,0<=m<=10000,1<=timei<=1000000,1<=ai,bi<=n。

题解

题意

给出一些关系：如 $A$要在 $B$之前遍历
每个点有点权
问遍历到 $i$的时候的最大点权和&最小点权和分别是多少

分析

注意到 $n$只有2000
考虑 $n^2$暴力
思考，最小点权和一定是从祖先一直都下来
那么可以建反向边，一直走即可
那么最大点权和就是要尽量先走其他点
那么就可以走正向边，把后继走完
再用总时间-后继时间即为答案

Code

#include<bits/stdc++.h>
#define rg register
using namespace std;
struct node
{int to,next;
}a[20005];
int n,m,sum,tot,s,val[2005],x[10005],y[10005],ans[2005][3],head[2005];
bool b[2005];
inline void add(int x,int y)
{tot++;a[tot].to=y;a[tot].next=head[x];head[x]=tot;
}
inline void dfs(int now)
{for (rg int i=head[now];i;i=a[i].next){if (b[a[i].to]==0){s+=val[a[i].to];b[a[i].to]=1;dfs(a[i].to);}}
}
int main()
{// freopen("test.in","r",stdin);// freopen("test.out","w",stdout);scanf("%d%d",&n,&m);for (rg int i=1;i<=n;++i){scanf("%d",&val[i]);sum+=val[i];}for (rg int i=1;i<=m;i++){scanf("%d%d",&x[i],&y[i]);add(y[i],x[i]);}printf("%d\n",sum);for (rg int i=1;i<=n;i++){s=0;memset(b,0,sizeof(b));b[i]=1;dfs(i);ans[i][1]=s+val[i];}// printf("%d\n",ans[1][1]);tot=0;memset(head,0,sizeof(head));for (rg int i=1;i<=m;i++)add(x[i],y[i]);for (rg int i=1;i<=n;i++){s=0;memset(b,0,sizeof(b));b[i]=1;dfs(i);ans[i][2]=sum-s;}for (rg int i=1;i<=n;i++)printf("%d %d\n",ans[i][1],ans[i][2]);return 0;
}