【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;
}