锐客网

  1. 首页 > it技术 > >

《随机题库练习10》G

【《随机题库练习10》G】思路：
看题就想到了拓扑.
但是由于这里可以同时进行多个安装.所以我先跑了一次dfs.(果然超时了).
首先这个答案肯定是有向边的最长边集的长度。(边的长度为安装时间)。
那么如果直接上拓扑,记录安装到每一个点的时间,然后通过前驱点不断转移。
这样是不行的.因为可能会存在多个前驱点。
我们需要取最长的前驱点作为开始安装的点，也就是说当我们入度删到0时,此时的前驱点应该是所有前驱点里安装到的时间最大的(因为可以同时进行多个安装)。所以我们采用优先队列来存点,并且引入安装时间来排序。保证了入度为0时的前驱点肯定是安装时间最大的这一条件.

#include using namespace std; typedef long long LL; typedef pair pii; const int N = 105; const int Mod = 1e6; #define pi acos(-1) #define INF 1e8 #define INM INT_MIN #define pb(a)push_back(a) #define mk(a,b) make_pair(a,b) #define dbg(x) cout << "now this num is " << x << endl; #define met0(axx) memset(axx,0,sizeof(axx)); #define metf(axx) memset(axx,-1,sizeof(axx)); #define sd(ax) scanf("%d",&ax) #define sld(ax) scanf("%lld",&ax) #define sldd(ax,bx) scanf("%lld %lld",&ax,&bx) #define sdd(ax,bx) scanf("%d %d",&ax,&bx) #define sddd(ax,bx,cx) scanf("%d %d %d",&ax,&bx,&cx) #define sfd(ax) scanf("%lf",&ax) #define sfdd(ax,bx) scanf("%lf %lf",&ax,&bx) #define pr(a) printf("%d\n",a) #define plr(a) printf("%lld\n",a) int in[1005],t[1005],arr[1005],ans; vector G[1005]; int main() { int n; sd(n); for(int i=1; i<=n; ++i) sd(t[i]); int m; sd(m); while(m--) { int x,y; sdd(x,y); G[y].pb(x); in[x]++; } priority_queue,greater > Q; for(int i=1; i<=n; ++i) { if(in[i] == 0) { arr[i] = t[i]; Q.push(pii(arr[i],i)); } } while(!Q.empty()) { int u = Q.top().second; Q.pop(); for(int i=0; i

    推荐阅读


    上一篇：珍惜资源|珍惜资源 爱我国土

    下一篇：《随机题库训练10》|《随机题库训练10》 A（）