题意就是给你一个有向无环图，并且告诉你：你可以任意删去k条边，问在删去k条边后字典序最小的拓扑排序的和也就是如果最后得出的拓扑排序是4 3 2 1 5，那么就应该输出4*1+3*2+2*3+1*4+5*5结果，最后结果要对1e9+7取模
思路：其实就是把普通的入度为1进队改为入队<=k 入队。
感觉这题数据有点水，貌似不需要判断重边。
代码：
#include<cstdio> #include<iostream> #include<vector> #include<queue> #include<set> #include<cstring> using namespace std; const int mod = 1e9 + 7; const int maxn = 1e5 + 10; typedef long long ll; typedef pair<int, int> pii; int in[maxn]; int vis[maxn]; int n, m,k; ll ans = 0; vector<int>vec[maxn]; void solve() { priority_queue<int, vector<int>, greater<int> >que; for (int i = 1; i <=n; i++) if (in[i] <= k) { que.push(i); vis[i] = 1; } int cnt = 1; while (!que.empty()) { int t = que.top(); que.pop(); if (in[t] > k)//如果t的入度小于现在的k，那么他就不能被算入本次的拓扑序列中。 { vis[t] = 0; continue; } k -= in[t]; (ans +=(ll)t*cnt%mod) %= mod;//这里的（ll）很重要哦 cnt++; for (int i = 0; i < vec[t].size(); i++) { int point = vec[t][i]; in[point]--; if (in[point] <= k && vis[point] == 0) { que.push(point); vis[point] = 1; } } } } void ini() { memset(vis, 0, sizeof(vis)); memset(in, 0, sizeof(in)); ans = 0; for (int i = 1; i <= n; i++) vec[i].clear(); } void getmap() { for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); vec[a].push_back(b); in[b]++; } } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d %d %d", &n, &m,&k); ini(); getmap(); solve(); cout << ans%mod << endl; } // system("pause"); return 0; }
