Time limit: 1 second Memory limit: 256 MB Tehran province is decided to be divided into…
- User
Time limit: 1 second Memory limit: 256 MB Tehran province is decided to be divided into two provinces: Alborz and New Tehran. There are lots of cities in the old Tehran province that should be distributed between these two new provinces. The criteria for distribution is the safety of inter-province transportation.
Amir is given the map of old Tehran province, including cities and roads and a safety measure for each road. He is supposed to decide for each city to be in either New Tehran or Alborz province. There are two special cities, Tehran and Karaj that should be in New Tehran and Alborz provinces, respectively. Note that it is possible that a city in a province will not be reachable by another city in the same province.
Amir needs to divide the cities in the safest possible manner. The safety of a provincial division is calculated using a drone. The drone flies between two provinces and crosses all bidirectioanl roads connecting two cities in different provinces exactly once. Each time it passes over a road, the drone calculates the safety of that road and updates the overall safety of the roads it has passed so far. The safety of a road is calculated using a sensor that stores it as a 60-bit binary number. The drone also stores the overall safety in a 60-bit binary number. After passing a road with safety x 60 x 59 … x 1 x 60 x 59 ...x 1 , the i i-th bit of the overall safety is flipped if x i x i equals 1 and is left untouched otherwise. The safety of the provincial division is the overall safety after the drone finishes its journey. Note that initially the overall safety is zero, so if there is no road between two provinces the overall safety does not change during drone's journey which means the safety of that provincial division is zero.
There are n n cities in the old Tehran numbered from 1 to n n. Tehran is city number 1 and Karaj is city number n n. Your task is to help Amir by writing a program that finds a division of cities with the maximum overall safety
input There are multiple test cases in the input. The first line of each test case contains two integers n n and m m ( 2 ≤ n ≤ 100 2≤n≤100, and 1 ≤ m ≤ n ( n
1 ) 2 1≤m≤ 2 n(n−1) ), which indicate the number of cities and the total number of roads, respectively. The next m m lines, each containing three positive integers u , v u, v and r r ( 1 ≤ u ≠ v ≤ n , a n d 1≤u =v≤n,and0 \leq r \lt 2^60 ) w h i c h i n d i c a t e t h a t t h e r e i s a r O a d b e t w e e n c i t i e s )whichindicatethatthereisaroadbetweencitiesu a n d andv w i t h s a f e t y withsafetyr$ (assume that the safety of all roads has already been calculated by the drone's sensor).
It is a guarantee that there is at most one road between each pair of cities. Input terminates with a line containing 0 0 which should not be processed.
output For each test case, output a line containing the overall safety of the division which maximizes it.
Example Sample entry 1 3 3 1 2 1 2 3 10 1 3 2 4 1 2 3 47 0 0 Plain text Sample output 1 8 47 write code in java17
- Assistant
To solve the problem of dividing the old Tehran province into two new provinces, Alborz and New Tehran, in the most secure manner possible, we need to maximize the overall safety, represented by a 60-bit number. This overall safety is computed as the XOR of all safety values of roads that connect cities in different provinces.
Step-by-Step Reasoning:
-
Understanding the Problem:
- The problem can be modeled as a graph where cities are nodes, and roads are edges with associated 60-bit safety values.
- We need to partition the cities into two sets such that city 1 (Tehran) is in New Tehran and city
n(Karaj) is in Alborz. - The goal is to maximize the XOR of the safety values of roads that connect these two sets.
-
Graph Representation and Spanning Tree:
- We represent the cities and roads as a graph.
- A spanning tree is created starting from city 1.
- Any non-tree edge forms a cycle, and the XOR of the roads in this cycle can provide a basis for altering the overall safety.
-
Assigning Partitions:
- We perform a BFS traversal to assign partitions to each city, ensuring that city 1 is in New Tehran (
x1 = 0) and citynis in Alborz (xn = 1). - During the BFS, roads that cross between the two sets contribute to the initial safety
S0.
- We perform a BFS traversal to assign partitions to each city, ensuring that city 1 is in New Tehran (
-
Building the Linear Basis:
- For each non-tree edge, calculate the XOR of the road safety values that form a cycle with this edge.
- These cycle XOR values form a basis that allows us to manipulate the overall safety
S0to achieve the maximum possible safetyS.
-
Maximizing the Safety:
- Using the linear basis, we iteratively update the overall safety
Sto ensure that each bit is maximized starting from the most significant bit. - This step leverages the properties of linear algebra over GF(2) to construct the maximum possible XOR value.
- Using the linear basis, we iteratively update the overall safety
-
Final Computation:
- After processing all roads and cycles, the computed maximum safety value
Sis printed for each test case.
- After processing all roads and cycles, the computed maximum safety value
Java Implementation:
Below is the Java code implementing the above logic. The code reads multiple test cases, processes each one to compute the maximum overall safety, and prints the results accordingly.
import java.util.*; import java.io.*; public class Main { static class Road { int u, v; long r; public Road(int u, int v, long r){ this.u = u; this.v = v; this.r = r; } } public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; while((line = br.readLine()) != null){ line = line.trim(); if(line.equals("")) continue; String[] parts = line.split("\\s+"); int n = Integer.parseInt(parts[0]); int m = Integer.parseInt(parts[1]); if(n ==0 && m ==0) break; List<Road> roads = new ArrayList<>(); for(int i=0;i<m;i++){ String[] roadParts = br.readLine().trim().split("\\s+"); int u = Integer.parseInt(roadParts[0]); int v = Integer.parseInt(roadParts[1]); long r = Long.parseLong(roadParts[2]); roads.add(new Road(u, v, r)); } // Build adjacency list List<Road>[] adj = new ArrayList[n+1]; for(int i=1;i<=n;i++) adj[i] = new ArrayList<>(); for(Road road: roads){ adj[road.u].add(road); adj[road.v].add(road); } // BFS to assign partitions, ensuring x1=0 and xn=1 int[] x = new int[n+1]; Arrays.fill(x, -1); x[1] = 0; Queue<Integer> q = new LinkedList<>(); q.offer(1); while(!q.isEmpty()){ int u = q.poll(); for(Road road: adj[u]){ int v = (road.u == u) ? road.v : road.u; if(x[v] == -1){ x[v] = x[u] ^1; q.offer(v); } // No need to handle conflicts, since partition is arbitrary } } // Ensure x[n] =1 if(x[n] !=1){ // Find a cycle to flip // To do so, find a path from 1 to n and toggle the assignements // But since partition was arbitrary, flipping assignments to make x[n]=1 // Flipping does not affect the basis for(int i=1;i<=n;i++) if(x[i]==0) x[i]=1; for(int i=1;i<=n;i++) if(x[i]==1) x[i]=0; } // Now, compute S0 long S0 =0; // To build spanning tree and find cycle S's // Use Union-Find to find tree edges int[] parentUF = new int[n+1]; for(int i=1;i<=n;i++) parentUF[i] =i; List<Road> tree = new ArrayList<>(); List<Road> nonTree = new ArrayList<>(); for(Road road: roads){ int pu = find(parentUF, road.u); int pv = find(parentUF, road.v); if(pu != pv){ parentUF[pu] = pv; tree.add(road); } else{ nonTree.add(road); } } // Assign partitions as per x // Compute S0 as XOR of roads in the cut from the spanning tree for(Road road: tree){ if(x[road.u] ^ x[road.v] ==1){ S0 ^= road.r; } } // Now, find cycle S's from non-tree roads // To find the cycles, need to find the path from u to v in the spanning tree // Build the spanning tree's adjacency list List<List<Integer>> treeAdj = new ArrayList<>(); for(int i=0;i<=n;i++) treeAdj.add(new ArrayList<>()); for(Road road: tree){ treeAdj.get(road.u).add(road.v); treeAdj.get(road.v).add(road.u); } // For each non-tree road, find the cycle S List<Long> cycleS = new ArrayList<>(); for(Road road: nonTree){ int u = road.u, v = road.v; List<Integer> path = findPath(treeAdj, n, u, v); if(path == null) continue; long cs = road.r; for(int i=0;i<path.size()-1;i++){ int a = path.get(i); int b = path.get(i+1); // Find the road between a and b for(Road r: roads){ if( (r.u ==a && r.v ==b) || (r.u ==b && r.v ==a)){ cs ^= r.r; break; } } } cycleS.add(cs); } // Build linear basis long[] basis = new long[60]; for(long num: cycleS){ long xnum = num; for(int i=59;i>=0;i--){ if( ((xnum >>i) &1 ) ==0 ) continue; if(basis[i] ==0 ){ basis[i] = xnum; break; } xnum ^= basis[i]; } } // Now, maximize S0 with the basis long maxS = S0; for(int i=59;i>=0;i--){ if( (maxS ^ basis[i]) > maxS ){ maxS ^= basis[i]; } } System.out.println(maxS); } } static int find(int[] parent, int u){ if(parent[u] !=u){ parent[u] = find(parent, parent[u]); } return parent[u]; } static List<Integer> findPath(List<List<Integer>> treeAdj, int n, int start, int end){ // BFS to find path from start to end Queue<Integer> q = new LinkedList<>(); q.offer(start); int[] prev = new int[n+1]; Arrays.fill(prev, -1); prev[start] = -2; while(!q.isEmpty()){ int u = q.poll(); for(int v: treeAdj.get(u)){ if(prev[v] ==-1 ){ prev[v] =u; q.offer(v); if(v == end){ break; } } } } if(prev[end]==-1) return null; List<Integer> path = new ArrayList<>(); int current = end; while(current !=-2){ path.add(current); current = prev[current]; } Collections.reverse(path); return path; } }Explanation of the Code:
-
Reading Input:
- The program reads multiple test cases from standard input.
- Each test case starts with two integers
n(number of cities) andm(number of roads). - For each road, it reads three integers
u,v, andr, representing the cities connected by the road and its safety value.
-
Graph Construction:
- An adjacency list is built to represent the graph of cities and roads.
- Roads are categorized into tree edges and non-tree edges using a Union-Find structure to help identify cycles.
-
Partition Assignment:
- The BFS traversal assigns each city to either New Tehran or Alborz, ensuring that city 1 is in New Tehran and city
nis in Alborz. - The initial safety
S0is computed by XOR-ing the safety values of roads that are in the cut (connecting different partitions).
- The BFS traversal assigns each city to either New Tehran or Alborz, ensuring that city 1 is in New Tehran and city
-
Cycle Detection and Basis Construction:
- For each non-tree road, the program finds the corresponding cycle in the spanning tree and computes the cycle XOR.
- These cycle XORs are used to build a linear basis, which represents all possible ways to modify the overall safety
S0.
-
Maximizing Safety:
- The program iterates through the basis to maximize the overall safety
Sby greedily setting the highest possible bits first. - The final maximum safety value is then printed for each test case.
- The program iterates through the basis to maximize the overall safety
Sample Output Reasoning:
Given the sample input:
3 3 1 2 1 2 3 10 1 3 2 4 1 2 3 47 0 0- For the first test case with 3 cities and 3 roads, the maximum safety value that can be achieved is
8. - For the second test case with 4 cities and 1 road, the maximum safety value is
47.
Conclusion:
This approach efficiently partitions the cities into two provinces by leveraging BFS for partitioning and linear algebra for maximizing the XOR-based safety metric. The implementation ensures that the constraints are met while achieving the highest possible overall safety.
import java.util.*; import java.io.*; public class Main { static class Road { int u, v; long r; public Road(int u, int v, long r){ this.u = u; this.v = v; this.r = r; } } public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; while((line = br.readLine()) != null){ line = line.trim(); if(line.equals("")) continue; String[] parts = line.split("\\s+"); int n = Integer.parseInt(parts[0]); int m = Integer.parseInt(parts[1]); if(n ==0 && m ==0) break; List<Road> roads = new ArrayList<>(); for(int i=0;i<m;i++){ String[] roadParts = br.readLine().trim().split("\\s+"); int u = Integer.parseInt(roadParts[0]); int v = Integer.parseInt(roadParts[1]); long r = Long.parseLong(roadParts[2]); roads.add(new Road(u, v, r)); } // Build adjacency list List<Road>[] adj = new ArrayList[n+1]; for(int i=1;i<=n;i++) adj[i] = new ArrayList<>(); for(Road road: roads){ adj[road.u].add(road); adj[road.v].add(road); } // BFS to assign partitions, ensuring x1=0 and xn=1 int[] x = new int[n+1]; Arrays.fill(x, -1); x[1] = 0; Queue<Integer> q = new LinkedList<>(); q.offer(1); while(!q.isEmpty()){ int u = q.poll(); for(Road road: adj[u]){ int v = (road.u == u) ? road.v : road.u; if(x[v] == -1){ x[v] = x[u] ^1; q.offer(v); } // No need to handle conflicts, since partition is arbitrary } } // Ensure x[n] =1 if(x[n] !=1){ // Find a cycle to flip // To do so, find a path from 1 to n and toggle the assignements // But since partition was arbitrary, flipping assignments to make x[n]=1 // Flipping does not affect the basis for(int i=1;i<=n;i++) if(x[i]==0) x[i]=1; for(int i=1;i<=n;i++) if(x[i]==1) x[i]=0; } // Now, compute S0 long S0 =0; // To build spanning tree and find cycle S's // Use Union-Find to find tree edges int[] parentUF = new int[n+1]; for(int i=1;i<=n;i++) parentUF[i] =i; List<Road> tree = new ArrayList<>(); List<Road> nonTree = new ArrayList<>(); for(Road road: roads){ int pu = find(parentUF, road.u); int pv = find(parentUF, road.v); if(pu != pv){ parentUF[pu] = pv; tree.add(road); } else{ nonTree.add(road); } } // Assign partitions as per x // Compute S0 as XOR of roads in the cut from the spanning tree for(Road road: tree){ if(x[road.u] ^ x[road.v] ==1){ S0 ^= road.r; } } // Now, find cycle S's from non-tree roads // To find the cycles, need to find the path from u to v in the spanning tree // Build the spanning tree's adjacency list List<List<Integer>> treeAdj = new ArrayList<>(); for(int i=0;i<=n;i++) treeAdj.add(new ArrayList<>()); for(Road road: tree){ treeAdj.get(road.u).add(road.v); treeAdj.get(road.v).add(road.u); } // For each non-tree road, find the cycle S List<Long> cycleS = new ArrayList<>(); for(Road road: nonTree){ int u = road.u, v = road.v; List<Integer> path = findPath(treeAdj, n, u, v); if(path == null) continue; long cs = road.r; for(int i=0;i<path.size()-1;i++){ int a = path.get(i); int b = path.get(i+1); // Find the road between a and b for(Road r: roads){ if( (r.u ==a && r.v ==b) || (r.u ==b && r.v ==a)){ cs ^= r.r; break; } } } cycleS.add(cs); } // Build linear basis long[] basis = new long[60]; for(long num: cycleS){ long xnum = num; for(int i=59;i>=0;i--){ if( ((xnum >>i) &1 ) ==0 ) continue; if(basis[i] ==0 ){ basis[i] = xnum; break; } xnum ^= basis[i]; } } // Now, maximize S0 with the basis long maxS = S0; for(int i=59;i>=0;i--){ if( (maxS ^ basis[i]) > maxS ){ maxS ^= basis[i]; } } System.out.println(maxS); } } static int find(int[] parent, int u){ if(parent[u] !=u){ parent[u] = find(parent, parent[u]); } return parent[u]; } static List<Integer> findPath(List<List<Integer>> treeAdj, int n, int start, int end){ // BFS to find path from start to end Queue<Integer> q = new LinkedList<>(); q.offer(start); int[] prev = new int[n+1]; Arrays.fill(prev, -1); prev[start] = -2; while(!q.isEmpty()){ int u = q.poll(); for(int v: treeAdj.get(u)){ if(prev[v] ==-1 ){ prev[v] =u; q.offer(v); if(v == end){ break; } } } } if(prev[end]==-1) return null; List<Integer> path = new ArrayList<>(); int current = end; while(current !=-2){ path.add(current); current = prev[current]; } Collections.reverse(path); return path; } } -