【Codeforces 427C】Checkposts
2024-09-21 02:07:23
【链接】 我是链接,点我呀:)
【题意】
环里面的点只需要一个点就能全都保护
问你最少需要多少花费以及最少的点才能将所有的点都保护
【题解】
有向图的强连通分量求出所有的联通分量
显然每个联通分量里面只需选择最小那个点就好
如果有多个最小的点,那么这个环就有多个选择。
每个环的最小点个数连乘一下就是方案数了
然后每个联通分量的最小值再全部都加起来就ok
【代码】
import java.io.*;
import java.util.*;
public class Main {
static InputReader in;
static PrintWriter out;
public static void main(String[] args) throws IOException{
//InputStream ins = new FileInputStream("E:\\rush.txt");
InputStream ins = System.in;
in = new InputReader(ins);
out = new PrintWriter(System.out);
//code start from here
new Task().solve(in, out);
out.close();
}
static int N = (int)1e5;
static class Task{
int n,m;
ArrayList g[] = new ArrayList[N+10],g1[] = new ArrayList[N+10];
int cost[] = new int[N+10];
int dfn[] = new int[N+10],low[] = new int[N+10];
boolean in[] = new boolean[N+10];
int mystack[] = new int[N+10];
int tot = 0,top = 0,totn = 0;
void dfs(int x) {
dfn[x] = low[x] = ++tot;
mystack[++top] = x;
in[x] = true;
int len = g[x].size();
for (int i = 0;i < len;i++) {
int y = (int)g[x].get(i);
if (dfn[y]==0) {
dfs(y);
low[x] = Math.min(low[x],low[y]);
}else
if (in[y] && dfn[y]<low[x]){
low[x] = dfn[y];
}
}
if (low[x]==dfn[x]) {
int v = 0;
totn++;
while (v!=x) {
v = mystack[top];
in[v] = false;
g1[totn].add(v);
top--;
}
}
}
public void solve(InputReader in,PrintWriter out) {
for (int i = 1;i <= N;i++) {
g[i] = new ArrayList();
g1[i] = new ArrayList();
}
n = in.nextInt();
for (int i = 1;i <= n;i++) cost[i] = in.nextInt();
m = in.nextInt();
for (int i = 1;i <= m;i++) {
int x,y;
x = in.nextInt();y = in.nextInt();
g[x].add(y);
}
for (int i = 1;i <= n;i++)
if (dfn[i]==0) dfs(i);
long ans = 0;
long way = 1;
for (int i = 1;i <= totn;i++) {
long mi = cost[(int)g1[i].get(0)];
long cnt = 1;
for (int j = 1;j < (int)g1[i].size();j++) {
int x = (int)g1[i].get(j);
x = cost[x];
if (x<mi) {
mi = x;
cnt = 1;
}else if (x==mi) cnt++;
}
ans = ans + mi;
way = (way*cnt)%((int)1e9 + 7);
}
out.println(ans+" "+way);
}
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader(InputStream ins) {
br = new BufferedReader(new InputStreamReader(ins));
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
最新文章
- js中网页高度与宽度那些事
- struts2所有组件
- js的client详解
- 【转】深入浅出Java三大框架SSH与MVC的设计模式
- poj 1004:Financial Management(水题,求平均数)
- hdu 2099
- STL学习系列一:STL(标准模板库)理论基础
- Ubuntu Server 14.04 下root无法ssh登陆
- javascript 向上滚动
- -_-#【Backbone】View
- 【转】gcc warning: braces around scalar initializer (标量初始化的括号)
- BZOJ 2875: [Noi2012]随机数生成器( 矩阵快速幂 )
- 备忘录模式设计模式入门Memento
- [微信小程序-开发工具]快捷键
- Java中HashMap源码分析
- 简单易上手的Bootstrap
- 【python3 自动化基础之pip】pip常用命令归类
- Can&#39;t find msguniq. Make sure you have GNU gettext tools 0.15 or newer installed
- unity UI如何开启(显示)或者关闭(隐藏)Panel界面最好?
- vue项目锚点的使用
热门文章
- Tomcat + solr5.2.1环境搭建
- “ResGen.exe”已退出,代码为 -1073741701 或 “ResGen.exe”已退出,代码为 2。
- P3626 [APIO2009]会议中心
- react hooks 全面转换攻略(一) react本篇之useState,useEffect
- 例题 3-5 谜题 uva227 Puzzle
- Jax
- NHibernate3.2学习笔记-几种查询方式
- Android 将Bitmap对象保存为png图片文件
- centos上安装supervisor来管理dotnetcore等应用程序
- (转)淘淘商城系列——使用solrj来测试索引库