Toposort

问题描述

给出nn个点mm条边的有向无环图. 要求删掉恰好kk条边使得字典序最小的拓扑序列尽可能小.

输入描述

输入包含多组数据. 第一行有一个整数TT, 表示测试数据组数. 对于每组数据: 第一行包含3个整数nn, mm和kk (1 \le n \le 100000, 0 \le k \le m \le 200000)(1≤n≤100000,0≤k≤m≤200000), 表示图中结点数目, 图中边的数目以及要删的边数. 接下来mm行, 每行包含两个整数u_iui and v_ivi, 表示存在一条u_iui到v_ivi的有向边 (1 \le u_i, v_i \le n)(1≤ui,vi≤n). 输入保证给定的图是一个DAG. 输入数据中nn的和不超过10^6106. 输入数据中mm的和不超过2 \cdot 10^62⋅106.

输出描述

对于每组数据, 输出一个整数S = (\displaystyle\sum_{i=1}^{n}{i\cdot p_i}) \text{ mod } (10^9 + 7)S=(i=1∑ni⋅pi) mod (109+7), 其中p_{1}, p_{2}, ..., p_{n}p1,p2,...,pn是字典序最小的那个拓扑序列.

输入样例

34 2 01 21 34 5 12 13 14 12 32 44 4 21 22 33 41 4

输出样例

题解：

参考下普通的用堆维护求字典序最小拓扑序, 用某种数据结构维护入度小于等于

这个数据结构可以用线段树, 建立一个线段树每个节点

复杂度 $O((n+m)\log n)O((n+m)logn)$

///1085422276#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include
           
            using namespace std;using namespace std ;typedef long long ll;#define mem(a) memset(a,0,sizeof(a))#define pb push_backconst int N=100000+50;const int mod = 1e9+7;const int inf = 1e9+7;int ind[N],head[N],t,n,m,K,vis[N];vector
            
              ans;vector
             
              G[N];struct ss { int l,r,sum,index;}tr[N*5];struct sss { int to,next;}e[N*20];void init() { t=1;mem(head);mem(ind);ans.clear();mem(vis); for(int i=0;i
              
               >1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); tr[k].sum=min(tr[k<<1].sum,tr[k<<1|1].sum);}int ask(int k,int s,int t,int c) { int ret; if(tr[k].l==tr[k].r&&tr[k].l==s) { return tr[k].index; } int mid=(tr[k].l+tr[k].r)>>1; if(tr[k<<1].sum<=c) { ret=ask(k<<1,s,mid,c); } else { ret=ask(k<<1|1,mid+1,t,c); } return ret;}void update(int k,int x,int c) { if(tr[k].l==tr[k].r&&tr[k].l==x) { tr[k].sum+=c; return ; } int mid=(tr[k].l+tr[k].r)>>1; if(x<=mid) update(k<<1,x,c); else update(k<<1|1,x,c); tr[k].sum=min(tr[k<<1].sum,tr[k<<1|1].sum);}int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&K); init();int u,v,check; for( int i=1;i<=m;i++) { scanf("%d%d",&u,&v); ind[v]++; G[u].pb(v); } build(1,1,n); for(int i=1;i<=n;i++) { check=ask(1,1,n,K); ans.pb(check); K-=ind[check]; update(1,check,inf); for(int j=0;j