@[kkkj](/user/638969) 你试试开墙运行下,检查问题 : )
或者发下代码?
by hegm @ 2023-04-07 07:17:39
@[hegm](/user/331947) 刚翻了一下么用欸
```java
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
n = nextInt();
m = nextInt();
weight = new int[n+1];
color = new int[n+1];
dfn = new int[n+1];
low = new int[n+1];
for (int i = 1; i <= n; i++)
weight[i] = nextInt();
for (int i = 0; i <= n; i++) {
link.add(new ArrayList<Integer>());
}
for (int i = 0; i < m; i++) {
int a = nextInt();
int b = nextInt();
link.get(a).add(b);
link.get(b).add(a);
}
for (int i = 1; i <= n; i++)
if(dfn[i] == 0)
tarjan(i);
new_weight = new int[c+1];
for (int i = 1; i <= n; i++) {
new_weight[color[i]] += weight[i];
}
int[] in_cnt = new int[c+1];
for (int i = 0; i < c+1; i++) {
new_link.add(new ArrayList<Integer>());
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < link.get(i).size(); j++) {
int next = link.get(i).get(j);
if(color[i] != color[next]) {
in_cnt[color[next]]++;
new_link.get(color[i]).add(color[next]);
}
}
}
int head = 1;
for (int i = 1; i < in_cnt.length; i++) {
if(in_cnt[i] == 0) head = i;
}
vis = new boolean[c+1];
dp = new int[c+1];
System.out.println(dfs(head));
}
static ArrayList<ArrayList<Integer>> new_link = new ArrayList<ArrayList<Integer>>();
static int[] dp, new_weight;
static boolean[] vis;
static int dfs(int pos) {
if(dp[pos]!=0)
return dp[pos];
vis[pos] = true;
int max = new_weight[pos];
for (int i = 0; i < new_link.get(pos).size(); i++) {
int next = new_link.get(pos).get(i);
if(vis[next]) continue;
max = Math.max(max, new_weight[pos] + dfs(next));
}
vis[pos] = false;
dp[pos] = max;
return max;
}
static ArrayList<ArrayList<Integer>> link = new ArrayList<ArrayList<Integer>>();
static int n, m;
static int[] weight;
static int[] color;
static int[] dfn;
static int[] low;
static Stack<Integer> stack = new Stack<Integer>();
static int c, d;
static void tarjan(int pos) {
dfn[pos] = ++d;
low[pos] = dfn[pos];
stack.add(pos);
for (int i = 0; i < link.get(pos).size(); i++) {
int next = link.get(pos).get(i);
if(dfn[next] == 0) {
tarjan(next);
low[pos] = Math.min(low[pos], low[next]);
}else if(color[next] == 0) {
low[pos] = Math.min(low[pos], dfn[next]);
}
}
if(dfn[pos] == low[pos]) {
color[pos] = ++c;
while(stack.peek() != pos) {
color[stack.pop()] = color[pos];
}
stack.pop();
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(br);
static int nextInt() throws IOException {
st.nextToken();
return (int)st.nval;
}
}
```
之前学tarjan就只拿了70分,3个RE,这次又刚学了一遍,也不知道自己写的对不对,不过代码也检查了好几遍,也没感觉出问题,最关键是WA我能接受,RE了本地运行却没问题,真是找不到问题所在
by kkkj @ 2023-04-07 07:24:17
@[kkkj](/user/638969) 草,你不是c++我调不了啊。
by hegm @ 2023-04-07 07:28:32
@[hegm](/user/331947) emm哈哈哈哈哈,没办法,我用的语言太小众了,在算法里?
by kkkj @ 2023-04-07 07:31:09
但是java在mc里可是重量级。
~~溜了,不会调~~
by hegm @ 2023-04-07 08:10:18
俺真是无语啦!!!!!!!去
P1726 上白泽慧音 运行了一下这个题的代码,稍微改了下输入输出,直接满分AC了,我到无所谓这道题过不过,但是这道模板题,RE完了我去下载数据到本地运行还不报错,结果也正确,我就是好想知道究竟是不是我写错了!!!!!!!。。。。。。。。但是现在没法证伪也没法证明正确,啊啊啊啊啊啊洛谷
by kkkj @ 2023-04-07 08:18:12
@[kkkj](/user/638969) 调不了,但是你这个代码在 #9 有几率 AC or RE,建议下载数据+断点DEBUG(java有吗)
by Limitless_lmw @ 2023-04-07 09:50:43