結果
| 問題 | No.119 旅行のツアーの問題 |
| ユーザー |
 夕叢霧香(ゆうむらきりか)
|
| 提出日時 | 2018-01-15 20:16:41 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 120 ms / 5,000 ms |
| コード長 | 5,558 bytes |
| コンパイル時間 | 2,530 ms |
| コンパイル使用メモリ | 79,372 KB |
| 実行使用メモリ | 54,000 KB |
| 最終ジャッジ日時 | 2023-08-25 17:55:03 |
| 合計ジャッジ時間 | 5,403 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 72 ms
52,984 KB |
| testcase_01 | AC | 100 ms
53,332 KB |
| testcase_02 | AC | 55 ms
50,544 KB |
| testcase_03 | AC | 54 ms
50,056 KB |
| testcase_04 | AC | 55 ms
50,180 KB |
| testcase_05 | AC | 84 ms
52,800 KB |
| testcase_06 | AC | 111 ms
54,000 KB |
| testcase_07 | AC | 55 ms
50,164 KB |
| testcase_08 | AC | 54 ms
50,096 KB |
| testcase_09 | AC | 54 ms
50,236 KB |
| testcase_10 | AC | 54 ms
50,300 KB |
| testcase_11 | AC | 54 ms
50,252 KB |
| testcase_12 | AC | 55 ms
50,228 KB |
| testcase_13 | AC | 55 ms
50,132 KB |
| testcase_14 | AC | 85 ms
52,796 KB |
| testcase_15 | AC | 61 ms
51,352 KB |
| testcase_16 | AC | 118 ms
53,736 KB |
| testcase_17 | AC | 55 ms
50,148 KB |
| testcase_18 | AC | 57 ms
50,236 KB |
| testcase_19 | AC | 60 ms
51,136 KB |
| testcase_20 | AC | 104 ms
53,568 KB |
| testcase_21 | AC | 111 ms
53,728 KB |
| testcase_22 | AC | 120 ms
53,812 KB |
ソースコード
import java.io.*;
import java.util.*;
class Main {
static final int I=100000;
static ArrayList<Long>[] g;
static int[][]mat;
static void add(int a, int b, int c){
g[a].add((long)b<<32|c);
mat[a][b]+=c;
}
@SuppressWarnings("unchecked")
public static void main(String[] args) {
MyScanner sc = new MyScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
int n=sc.nextInt();
int[]b=new int[n],c=new int[n];
g=new ArrayList[3*n+2];
Arrays.setAll(g,x->new ArrayList<Long>());
mat=new int[3*n+2][3*n+2];
for(int i=0;i<n;++i){
b[i]=sc.nextInt();
c[i]=sc.nextInt();
add(0,2+n+i,150-b[i]);
add(2+n+i,2+2*n+i,150);
add(2+2*n+i,2+n+i,I);
add(2+2*n+i,1,150-c[i]);
}
int m=sc.nextInt();
for(int i=0;i<m;++i){
int d=sc.nextInt();
int e=sc.nextInt();
add(2+2*n+e,2+n+d,I);
}
MaxFlow mf = new MaxFlow();
long ans=mf.fordFulkerson(mat,0,1);
out.println(150*n-ans);
out.close();
}
// http://codeforces.com/blog/entry/7018
//-----------PrintWriter for faster output---------------------------------
public static PrintWriter out;
//-----------MyScanner class for faster input----------
public static class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine(){
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
int[] nextIntArray(int n){
int[]r=new int[n];
for(int i=0;i<n;++i)r[i]=nextInt();
return r;
}
}
}
class MaxFlow
{
/* Returns true if there is a path from source 's' to sink
't' in residual graph. Also fills parent[] to store the
path */
boolean bfs(int rGraph[][], int s, int t, int parent[])
{
// Create a visited array and mark all vertices as not
// visited
int V=rGraph.length;
boolean visited[] = new boolean[V];
for(int i=0; i<V; ++i)
visited[i]=false;
// Create a queue, enqueue source vertex and mark
// source vertex as visited
LinkedList<Integer> queue = new LinkedList<Integer>();
queue.add(s);
visited[s] = true;
parent[s]=-1;
// Standard BFS Loop
while (queue.size()!=0)
{
int u = queue.poll();
for (int v=0; v<V; v++)
{
if (visited[v]==false && rGraph[u][v] > 0)
{
queue.add(v);
parent[v] = u;
visited[v] = true;
}
}
}
// If we reached sink in BFS starting from source, then
// return true, else false
return (visited[t] == true);
}
// Returns tne maximum flow from s to t in the given graph
int fordFulkerson(int graph[][], int s, int t)
{
int u, v;
// Create a residual graph and fill the residual graph
// with given capacities in the original graph as
// residual capacities in residual graph
// Residual graph where rGraph[i][j] indicates
// residual capacity of edge from i to j (if there
// is an edge. If rGraph[i][j] is 0, then there is
// not)
int V=graph.length;
int rGraph[][] = new int[V][V];
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
// This array is filled by BFS and to store path
int parent[] = new int[V];
int max_flow = 0; // There is no flow initially
// Augment the flow while tere is path from source
// to sink
while (bfs(rGraph, s, t, parent))
{
// Find minimum residual capacity of the edhes
// along the path filled by BFS. Or we can say
// find the maximum flow through the path found.
int path_flow = Integer.MAX_VALUE;
for (v=t; v!=s; v=parent[v])
{
u = parent[v];
path_flow = Math.min(path_flow, rGraph[u][v]);
}
// update residual capacities of the edges and
// reverse edges along the path
for (v=t; v != s; v=parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
// Add path flow to overall flow
max_flow += path_flow;
}
// Return the overall flow
return max_flow;
}
}