欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 5638 Toposort 拓扑排序 优先队列

程序员文章站 2024-03-19 09:50:52
...

Toposort

题目连接:

http://acm.hdu.edu.cn/showproblem.php?pid=5638

Description

There is a directed acyclic graph with n vertices and m edges. You are allowed to delete exact k edges in such way that the lexicographically minimal topological sort of the graph is minimum possible.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains three integers n, m and k (1≤n≤100000,0≤k≤m≤200000) -- the number of vertices, the number of edges and the number of edges to delete.

For the next m lines, each line contains two integers ui and vi, which means there is a directed edge from ui to vi (1≤ui,vi≤n).

You can assume the graph is always a dag. The sum of values of n in all test cases doesn't exceed 106. The sum of values of m in all test cases doesn't exceed 2×106.

Output

For each test case, output an integer S=(∑i=1ni⋅pi) mod (109+7), where p1,p2,...,pn is the lexicographically minimal topological sort of the graph.

Sample Input

3
4 2 0
1 2
1 3
4 5 1
2 1
3 1
4 1
2 3
2 4
4 4 2
1 2
2 3
3 4
1 4

Sample Output

30
27
30

Hint

题意

给一个DAG,然后让你最多删除k条边,使得这个图的拓扑序最小。

题解:

贪心的想一想,现在我扔出来的点是一定是入度小于等于k,且编号最小的点。

这个怎么做呢?

线段树内二分,或者直接优先队列就好了。

choose what you like.

代码

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 2e5+7;
const int mod = 1e9+7;
vector<int> E[maxn],rE[maxn];
int in[maxn];
int inq[maxn];
int vis[maxn];
priority_queue<int,vector<int>,greater<int> >Q;
void init()
{
    for(int i=0;i<maxn;i++)
        E[i].clear(),rE[i].clear(),in[i]=0;
    memset(inq,0,sizeof(inq));
    memset(vis,0,sizeof(vis));
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<m;i++)
        {
            int x,y;scanf("%d%d",&x,&y);
            E[x].push_back(y);
            rE[y].push_back(x);
            in[y]++;
        }
        long long Ans = 0;
        for(int i = 1 ; i <= n ; ++ i)
        {
            if(in[i]<=k)
            {
                Q.push( i );
                inq[i] = 1;
            }
        }
        int num = 1;
        while(!Q.empty()){
            int x = Q.top() ; Q.pop(); inq[x] = 0;
            if(k >= in[x]){
                vis[x] = 1 , k -= in[x];
                Ans=(Ans+1ll*num*x)%mod;
                num=num+1;
                for(int i=0;i<E[x].size();i++){
                    int v =E[x][i];
                    if(vis[v]) continue;
                    in[v]--;
                    if(in[v] <= k&&!inq[v]){
                        Q.push(v);
                        inq[v] = 1;
                    }
                }
            }
        }
        printf("%I64d\n",Ans);
    }
}

上一篇: MD5算法常见坑

下一篇: MD5散列算法