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

题目

Description

Input

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

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;

}