Toposort

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 499 Accepted Submission(s): 203

Problem 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

思路：

和上道hdu 5195差不多，改点东西就行了。。之前疯狂超时，找了一个小时找不到哪里出了问题，最后问了下徐巨，发现vector忘了清空，清空下就好了。

实现代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define mid ll m = (l + r) >> 1

const int M = 2e5+;

const int inf = 0x3f3f3f3f;

const int md = 1e9+;

ll n,m,cnt,key;

vector<ll>g[M];

ll sum[M<<],du[M];

void pushup(ll rt){

    sum[rt] = min(sum[rt<<],sum[rt<<|]);

}

void build(ll l,ll r,ll rt){

    if(l == r){

        sum[rt] = du[l];

        return;

    }

    mid;

    build(lson);

    build(rson);

    pushup(rt);

}

void update(ll p,ll l,ll r,ll rt){

    if(l == r){

        sum[rt]--;

        return ;

    }

    mid;

    if(p <= m) update(p,lson);

    else  update(p,rson);

    pushup(rt);

}

void query(ll l,ll r,ll rt){

    if(l == r){

        cnt -= sum[rt];

        key = l;

        sum[rt] = inf;

        return ;

    }

    mid;

    if(sum[rt<<] <= cnt) query(lson);

    else query(rson);

    pushup(rt);

}

int main(){

    ll u,v;

    ll t;

    scanf("%lld",&t);

    while(t--){

        scanf("%lld%lld%lld",&n,&m,&cnt);

        for(ll i = ;i <= m;i ++){

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

            g[u].push_back(v);

            du[v]++;

        }

        build(,n,);

        ll ans = ;

        for(ll i = ;i <= n;i ++){

            query(,n,);

            ans=(ans+key*i)%md;

            for(ll j = ;j < g[key].size();j++){

                ll x = g[key][j];

                update(x,,n,);

            }

        }

        printf("%lld\n",ans);

        memset(du,,sizeof(du));

        memset(sum,inf,sizeof(sum));

        for(ll i=;i<=n;i++)

            g[i].clear();

    }

    return ;

}

巴特西

hdu 5638 Toposort (拓扑排序+线段树）

Toposort

最新文章

热门文章