首页 > 代码库 > Codeforces Round #244 (Div. 2)——Checkposts
Codeforces Round #244 (Div. 2)——Checkposts
题目链接
- 题意:
给定n个点,每个点有一个权值的有向图。现在需要选定一些点,使得这些点权值和最小,且满足:如果i能到达j且j能到达i,那么i、j可以只选一个 - 分析:
强联通模板题
//使用时只更新G完成构图 //scc_cnt从1开始计数 //pre[]表示点在DFS树中的先序时间戳 //lowlink[]表示当前点和后代能追溯到的最早祖先的pre值 //sccno[]表示点所在的双连通分量编号 //vector<int> G保存每个点相邻的下一个点序号 //stack<Edge> S是算法用到的栈 const int MAXV = 310000; vector<int> G[MAXV]; int pre[MAXV], lowlink[MAXV], sccno[MAXV], dfs_clock, scc_cnt; stack<int> S; void init(int n) { REP(i, n) G[i].clear(); } void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; S.push(u); for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(!pre[v]) { dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); } else if(!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); } } if(lowlink[u] == pre[u]) { scc_cnt++; for(;;) { int x = S.top(); S.pop(); sccno[x] = scc_cnt; if(x == u) break; } } } void find_scc(int n) { dfs_clock = scc_cnt = 0; memset(sccno, 0, sizeof(sccno)); memset(pre, 0, sizeof(pre)); for(int i = 0; i < n; i++) if(!pre[i]) dfs(i); }; int cost[MAXV]; vector<int> vt[MAXV]; int Min[MAXV]; int main() { // freopen("in.txt", "r", stdin); int n, e, a, b; while (~RI(n)) { init(n); REP(i, MAXV) vt[i].clear(); CLR(Min, INF); REP(i, n) RI(cost[i]); RI(e); REP(i, e) { RII(a, b); a--; b--; G[a].push_back(b); } find_scc(n); REP(i, n) { int no = sccno[i]; vt[no].push_back(i); Min[no] = min(Min[no], cost[i]); } LL v = 0, ans = 1; REP(i, MAXV) { if (vt[i].size() > 0) { int cnt = 0; REP(j, vt[i].size()) { if (cost[vt[i][j]] == Min[i]) cnt++; } ans *= cnt; ans %= MOD; v += Min[i]; } } cout << v << ‘ ‘ << ans << endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。