Problem Description
n vertices and m edges. You are allowed to delete exact k
Input
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
S=(∑i=1ni⋅pi) mod (109+7), where p1,p2,...,pn
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
有向图删除k条边使得拓扑序列字典序最小，可以直接用优先队列维护。
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
const int mod=1e9+7;
int T,n,m,k,cnt[maxn],x,y,vis[maxn];
vector<int> t[maxn];
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++) t[i].clear(),cnt[i]=vis[i]=0;
while (m--)
{
scanf("%d%d",&x,&y);
t[x].push_back(y);
cnt[y]++;
}
priority_queue<int,vector<int>,greater<int> > p;
for (int i=1;i<=n;i++) if (cnt[i]<=k) p.push(i),vis[i]=1;
int res=0,i=1;
while (!p.empty())
{
int q=p.top(); p.pop();
if (cnt[q]>k) {vis[q]=0; continue;}
(res+=(LL)q*i++%mod)%=mod;
k-=cnt[q];
for (int i=0;i<t[q].size();i++)
{
cnt[t[q][i]]--;
if (!vis[t[q][i]]&&cnt[t[q][i]]<=k)
{
p.push(t[q][i]);
vis[t[q][i]]=1;
}
}
}
printf("%d\n",res);
}
return 0;
}