Reward

发工资，以前看过这题，做没做忘了（应该是没做）。

很明显的拓排。但数据范围这么大，吓得我当时就不敢动手。后来找题解发现还是相当于两层循环（are you kidding me?）当时卡在了不造怎么分层累加，比如4个人，2个关系，1>2,3>4。那么1，3在同一层，2，4在同一层。

题意：年终奖金最低888，但员工间有要求，n个员工，m个要求，m行每行两个数代表前一个人的工资要多于后一个人的。为了满足所有员工的要求，问boss最少需要多少money。

思路：二维数组爆内存，看到几个MLE的让我笑会。用vector存图，把前一个存进后一个里，前一个的度加一。q[v].push_back(u)，好吧，比赛的时候，没想到要这样的。然后把所有度为0的放进队列里面。其实这就在计算第一层了。把与这些点相连的点的度全部减一，再把度变为0的点又加进队列里（第二层的）。重复操作。。判环可以把整个过程度为0的数量计算出来，再与n比较，也可以在最终队列结束后一层循环判断是否有度大于0的点，因为正常情况下所有的点都会进入队列一次，有环的话则度不会减为0也不会进入队列。

const int N=1e4+10;

vector<int>q[N];

queue<int>que;

int n,m,du[N],now;

void init()

{

    now=888;//第0层的工资即初始工资；

    for(int i=0; i<=n; i++) q[i].clear();

    memset(du,0,sizeof(du));

    while(!que.empty()) que.pop();

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        init();

        int u,v;

        while(m--)

        {

            scanf("%d%d",&u,&v);

            q[v].push_back(u);//逆拓排；

            du[u]++;

        }

        int cnt=0;

        for(int i=1; i<=n; i++)

            if(!du[i])

            {

                que.push(i);

                cnt++;

            }

        int ans=0;

        while(!que.empty())

        {

            int size=que.size();

            while(size--)//按层累加

            {

                int v=que.front();

                que.pop();

                ans+=now;

                for(int i=0; i<q[v].size(); i++)

                {

                    int u=q[v][i];

                    du[u]--;

                    if(!du[u])

                    {

                        que.push(u);

                        cnt++;

                    }

                }

            }

            now++;

        }

        int f=0;

        for(int i=1;i<=n&&!f;i++)

            if(du[i]) f=1;

        if(f) printf("-1\n");

        else printf("%d\n",ans);

    }

    return 0;

}

这样没超时我是比较奇怪的，拓排运用的并不是很多，也不是很熟练，这样也算加深对知识点的理解运用吧。

巴特西

HDU-2647 Reward ，逆拓排。

Reward

最新文章

热门文章