注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
进来问下关于第三周的编程作业题。我的答案总是20,试了一下不正确。但是用这段代码测试的小样本都是正确的,手动试了一下,也没有觉得有什么问题。不明白错在那里了。下面是结题思路:
我用java自己建的数据结构。总的来说,图的存储的方式是:使用一个map存 <顶点, 该顶点相邻的顶点>。
对于删除一个边(将两个顶点合为一个)的操作是(假设删除node1 和node2 的link,存为node1)
1. 找到node2的所有相邻点,
a. 如果该相邻点为node1,则continue;
b. 将其他所有相邻点 添加到node1的相邻点列表中,并且node1也会成为这些点的相邻点;
c. 将node2从所有相邻点的邻点列表中删除;
2. 删除node2.
重复整个步骤直到图中只剩下两个点。这两个点的相邻点个数相同,返回这个个数就是min cut。
代码在下面。希望找到问题的人可以指教下 , 先谢谢了- import java.io.BufferedReader;
- import java.io.FileNotFoundException;
- import java.io.FileReader;
- import java.io.IOException;
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.HashMap;
- import java.util.HashSet;
- import java.util.LinkedList;
- import java.util.List;
- import java.util.Map;
- import java.util.Random;
- import java.util.Set;
- public class minCut{
- Graph1 graph;
-
- public minCut(){
- graph = new Graph1();
- }
-
- public ArrayList<Node> findMinCut(int[][] matrix){
- graph.buildMap(matrix);
-
- while(graph.getSize()>2){
- Node node1 = graph.getNode(graph.giveRandomIndex());
- Node node2 = graph.getNode(graph.giveRandomIndex());
-
- while(node2 == node1){
- node2 = graph.getNode(graph.giveRandomIndex());
- }
- graph.cutEdge(node1, node2);
- }
- Node lastNode =graph.getNode(graph.giveRandomIndex());
- /*while(graph.getNeigbhors(lastNode).contains(lastNode)){
- graph.getNeigbhors(lastNode).remove(lastNode);
- }*/
- //return graph.getNeigbhors(lastNode).size();
- ArrayList<Node> neighbors;
- if (graph.getNeigbhors(lastNode).size() == 3){
- neighbors = graph.getNeigbhors(lastNode);
- neighbors.add(lastNode);
- return neighbors;
- }
- return null;
- }
-
- public static void main(String[] args) throws NumberFormatException, IOException{
- /*int[][] matrix = {{1,2,6,0,0,0},{2,1,3,4,5,6},{3,2,0,0,0,0},{4,2,5,0,0,0},{5,2,4,6,0,0},{6,1,2,5,0,0}};
- minCut mincut = new minCut();
-
- int number = mincut.findMinCut(matrix);
- System.out.println(number);*/
- // int[][] matrix = {{1,2,3,4,7},{2,1,3,4,0},{3,1,2,4,0},{4,1,2,3,5},{5,4,6,7,8},{6,5,7,8,0},{7,1,5,6,8},{8,5,6,7,0}};
-
-
- BufferedReader bf = new BufferedReader(new FileReader("data4.txt"));
- String line;
- int[][] matrix = new int[40][8];
- int i=0;
-
-
- while((line = bf.readLine())!=null){
- String[] chars = line.split("\\s+");
- int j=0;
- for(String integer: chars){
- matrix[i][j] = Integer.parseInt(integer);
- j++;
- }
- i++;
- }
-
-
- /*minCut mincut;
- for(int iter = 0 ;iter<1000; iter++){*/
-
- int number =1000;
- for(int iter = 0 ;iter<500000; iter++){
- minCut mincut = new minCut();
- ArrayList<Node> update = mincut.findMinCut(matrix);
- if(update!= null)
- System.out.println(update);
- }
- }
- }
- class Graph1{
-
- private static Map<Node,ArrayList<Node>> map;
-
- public Graph1(){
- map = new HashMap<Node,ArrayList<Node>>();
- }
-
- public Set<Node> getAllNodes(){
- return Collections.unmodifiableSet(map.keySet());
- }
-
- public void addNode(Node n){
- if(map.containsValue(n)) return ;
- map.put(n, new ArrayList<Node>());
- }
-
- public static ArrayList<Node> getNeigbhors(Node n){
- return map.get(n);
- }
-
- public static void addNeighbor(Node des, Node rcs){
- map.get(des).add(rcs);
- }
-
- /*public static void deleteNeighbor(Node des, Node rcs){
- map.get(des).remove(rcs);
- }*/
-
- public static void deleteNode(Node node){
- if(!map.containsKey(node)) return ;
- for(Node neighbors:getNeigbhors(node) )
- map.get(neighbors).remove(node);
- map.get(node).clear();
- map.remove(node);
- }
-
- public int getSize(){
- Set<Node> allNode = getAllNodes();
- return allNode.size();
- }
-
- public int giveRandomIndex(){
- Set<Node> allNode = getAllNodes();
- int size = allNode.size();
- int item = new Random().nextInt(size);
- int i = 0;
- for(Node node:allNode){
- if(i == item)
- return node.getNodeIndex();
- i++;
- }
- return -1;
- }
-
-
- public void buildMap(int[][] matrix){
-
- List<Node> list = new LinkedList<Node>();
- for(int i =0; i<matrix.length;i++){
- Node node = new Node(matrix[i][0]);
- addNode(node);
- list.add(node);
- }
-
-
- int i=0;
- for(Node des:list){
- for(int j =1; j<matrix[0].length; j++){
- if(matrix[i][j]==0) continue;
- Node src = getNode(matrix[i][j]);
- addNeighbor(des , src);
- }
- i++;
- }
- }
-
-
- /**
- * Give parameter index x , getNode should return the corresponding Node which has this index
- * @param x.
- * @return
- */
- public Node getNode(int x){
- for(Node node:Collections.unmodifiableCollection(map.keySet())){
- if(node.getNodeIndex()==x)
- return node;
- }
- return null;
- }
-
- /**
- * cutEdge is used to merge two Node n1 and n2 into one Node n1
- * @param n1 n1 will not vanish after cutting, n2's neighbors will be added to it.
- * @param n2 n2's neighbors will be added to n1. All it's neighbors will delete n2 as neighbor; And n2 is deleted afterwards;
- */
- public void cutEdge(Node n1, Node n2){
- for(Node node:getNeigbhors(n2)){
- if(n1 == node) // this means if n2's neighbor is n1 itself, we don't have to include it into n1's neighbor group.
- continue;
- addNeighbor(n1, node);
- addNeighbor(node, n1);
- }
- deleteNode(n2);
- }
- }
- class Node{
- private int index;
- //private ArrayList<Node> neighbors = new ArrayList<Node>();
-
- public Node(int x){ /*, ArrayList<Node> neighbors*/
- this.index = x;
- // this.neighbors = neighbors;
- }
-
- public int getNodeIndex(){
- return index;
- }
-
- public String toString(){
- String result = "Node: "+getNodeIndex();
- return result;
- }
- }
复制代码 |