結果
| 問題 |
No.3201 Corporate Synergy
|
| コンテスト | |
| ユーザー |
 伟国姚
|
| 提出日時 | 2025-07-11 22:50:48 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 87 ms / 2,000 ms |
| コード長 | 9,681 bytes |
| コンパイル時間 | 4,998 ms |
| コンパイル使用メモリ | 83,876 KB |
| 実行使用メモリ | 44,484 KB |
| 最終ジャッジ日時 | 2025-07-11 22:50:57 |
| 合計ジャッジ時間 | 6,197 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 |
ソースコード
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static final class MaxFlow {
private static final class InternalCapEdge {
final int to;
final int rev;
long cap;
InternalCapEdge(int to, int rev, long cap) {
this.to = to;
this.rev = rev;
this.cap = cap;
}
}
public static final class CapEdge {
public final int from, to;
public final long cap, flow;
CapEdge(int from, int to, long cap, long flow) {
this.from = from;
this.to = to;
this.cap = cap;
this.flow = flow;
}
@Override
public boolean equals(Object o) {
if (o instanceof CapEdge) {
CapEdge e = (CapEdge) o;
return from == e.from && to == e.to && cap == e.cap && flow == e.flow;
}
return false;
}
}
private static final class IntPair {
final int first, second;
IntPair(int first, int second) {
this.first = first;
this.second = second;
}
}
static final long INF = Long.MAX_VALUE;
private final int n;
private final java.util.ArrayList<IntPair> pos;
private final java.util.ArrayList<InternalCapEdge>[] g;
@SuppressWarnings("unchecked")
public MaxFlow(int n) {
this.n = n;
pos = new java.util.ArrayList<>();
g = new java.util.ArrayList[n];
for (int i = 0; i < n; i++) {
g[i] = new java.util.ArrayList<>();
}
}
public int addEdge(int from, int to, long cap) {
rangeCheck(from, 0, n);
rangeCheck(to, 0, n);
nonNegativeCheck(cap, "Capacity");
int m = pos.size();
pos.add(new IntPair(from, g[from].size()));
int fromId = g[from].size();
int toId = g[to].size();
if (from == to) toId++;
g[from].add(new InternalCapEdge(to, toId, cap));
g[to].add(new InternalCapEdge(from, fromId, 0L));
return m;
}
private InternalCapEdge getInternalEdge(int i) {
return g[pos.get(i).first].get(pos.get(i).second);
}
private InternalCapEdge getInternalEdgeReversed(InternalCapEdge e) {
return g[e.to].get(e.rev);
}
public CapEdge getEdge(int i) {
int m = pos.size();
rangeCheck(i, 0, m);
InternalCapEdge e = getInternalEdge(i);
InternalCapEdge re = getInternalEdgeReversed(e);
return new CapEdge(re.to, e.to, e.cap + re.cap, re.cap);
}
//求所有边的流量，容量情况
public CapEdge[] getEdges() {
CapEdge[] res = new CapEdge[pos.size()];
Arrays.setAll(res, this::getEdge);
return res;
}
public void changeEdge(int i, long newCap, long newFlow) {
int m = pos.size();
rangeCheck(i, 0, m);
nonNegativeCheck(newCap, "Capacity");
if (newFlow > newCap) {
throw new IllegalArgumentException(
String.format("Flow %d is greater than the capacity %d.", newCap, newFlow));
}
InternalCapEdge e = getInternalEdge(i);
InternalCapEdge re = getInternalEdgeReversed(e);
e.cap = newCap - newFlow;
re.cap = newFlow;
}
public long maxFlow(int s, int t) {
return flow(s, t, INF);
}
public long flow(int s, int t, long flowLimit) {
rangeCheck(s, 0, n);
rangeCheck(t, 0, n);
long flow = 0L;
int[] level = new int[n];
int[] que = new int[n];
int[] iter = new int[n];
while (flow < flowLimit) {
bfs(s, t, level, que);
if (level[t] < 0) break;
Arrays.fill(iter, 0);
while (flow < flowLimit) {
long d = dfs(t, s, flowLimit - flow, iter, level);
if (d == 0) break;
flow += d;
}
}
return flow;
}
private void bfs(int s, int t, int[] level, int[] que) {
Arrays.fill(level, -1);
int hd = 0, tl = 0;
que[tl++] = s;
level[s] = 0;
while (hd < tl) {
int u = que[hd++];
for (InternalCapEdge e : g[u]) {
int v = e.to;
if (e.cap == 0 || level[v] >= 0) continue;
level[v] = level[u] + 1;
if (v == t) return;
que[tl++] = v;
}
}
}
private long dfs(int cur, int s, long flowLimit, int[] iter, int[] level) {
if (cur == s) return flowLimit;
long res = 0;
int curLevel = level[cur];
for (int itMax = g[cur].size(); iter[cur] < itMax; iter[cur]++) {
int i = iter[cur];
InternalCapEdge e = g[cur].get(i);
InternalCapEdge re = getInternalEdgeReversed(e);
if (curLevel <= level[e.to] || re.cap == 0) continue;
long d = dfs(e.to, s, Math.min(flowLimit - res, re.cap), iter, level);
if (d <= 0) continue;
e.cap += d;
re.cap -= d;
res += d;
if (res == flowLimit) break;
}
return res;
}
//求最小割
public boolean[] minCut(int s) {
rangeCheck(s, 0, n);
boolean[] visited = new boolean[n];
int[] stack = new int[n];
int ptr = 0;
stack[ptr++] = s;
visited[s] = true;
while (ptr > 0) {
int u = stack[--ptr];
for (InternalCapEdge e : g[u]) {
int v = e.to;
if (e.cap > 0 && !visited[v]) {
visited[v] = true;
stack[ptr++] = v;
}
}
}
return visited;
}
private void rangeCheck(int i, int minInclusive, int maxExclusive) {
if (i < 0 || i >= maxExclusive) {
throw new IndexOutOfBoundsException(
String.format("Index %d out of bounds for length %d", i, maxExclusive));
}
}
private void nonNegativeCheck(long cap, String attribute) {
if (cap < 0) {
throw new IllegalArgumentException(String.format("%s %d is negative.", attribute, cap));
}
}
}
public static void main(String[] args) {
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int m = sc.nextInt();
int[][] e = new int[m][2];
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
e[i][j] = sc.nextInt() - 1;
}
}
int k = sc.nextInt();
int S = n + k, T = S + 1;
MaxFlow flow = new MaxFlow(T + 1);
long sum = 0;
for (int i = 0; i < n; i++) {
/* if (a[i] > 0) {
flow.addEdge(i, T, a[i]);
// sum += a[i];
} else {
flow.addEdge(S, i, -a[i]);
}*/
if (a[i] >= 0) {
// 正利润：源点→i
flow.addEdge(S, i, a[i]);
sum += a[i];
} else {
// 负利润：i→汇点
flow.addEdge(i, T, -a[i]);
}
}
for (int[] ee : e) {
int u = ee[0], v = ee[1];
//v 依赖于 u
//选 v 的话必须选 u
flow.addEdge(v, u, 1L << 60);
}
for (int i = 0; i < k; i++) {
int u = sc.nextInt() - 1, v = sc.nextInt() - 1, s = sc.nextInt();
// flow.addEdge(u, i + n, 1L << 60);
// flow.addEdge(v, i + n, 1L << 60);
flow.addEdge(i + n, u, 1L << 60);
flow.addEdge(i + n, v, 1L << 60);
// flow.addEdge(i + n, T, s);
flow.addEdge(S, i + n, s);
sum += s;
}
long l = flow.maxFlow(S, T);
out.println(Math.max(0, sum - l));
out.close();
}
static Kattio sc = new Kattio();
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static class Kattio {
static BufferedReader r;
static StringTokenizer st;
public Kattio() {
r = new BufferedReader(new InputStreamReader(System.in));
}
public String next() {
try {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(r.readLine());
}
return st.nextToken();
} catch (Exception e) {
return null;
}
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}