1 import java.io.*;
2 import java.util.*;
3 /*
4 ID: yanglei4
5 LANG: JAVA
6 TASK:fence6
7 */
8 public class fence6 {
9 public static void main(String[] args) throws IOException {
10 BufferedReader f = new BufferedReader(new FileReader("fence6.in"));
11 PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("fence6.out")));
12 int N = Integer.parseInt(f.readLine());
13 int[][] D = new int[N * 2][N * 2];
14 //init D
15 for (int i = 0; i < N * 2; i++)
16 for (int j = 0; j < N * 2; j++)
17 D[i][j] = -1;
18
19 int PointCount = 0;
20 int[][] PointsDesc = new int[2 * N][N + 1];
21 int[][] LineDesc = new int[N + 1][2];
22
23 //input and create the matrix
24 for (int i = 0; i < N; i++) {
25 StringTokenizer st = new StringTokenizer(f.readLine());
26 int LineNumber = Integer.parseInt(st.nextToken());
27 int LineLength = Integer.parseInt(st.nextToken());
28 int LeftCount = Integer.parseInt(st.nextToken());
29 int RightCount = Integer.parseInt(st.nextToken());
30
31 int[] LeftPoints = new int[LeftCount];
32 int[] RightPoints = new int[RightCount];
33
34 //Read the Left Points
35 st = new StringTokenizer(f.readLine());
36 for (int j = 0; j < LeftCount; j++)
37 LeftPoints[j] = Integer.parseInt(st.nextToken());
38
39 //Read the Right Pints
40 st = new StringTokenizer(f.readLine());
41 for (int j = 0; j < RightCount; j++)
42 RightPoints[j] = Integer.parseInt(st.nextToken());
43
44 int firstpoint = -1;
45 int secondpoint = -1;
46
47 //Find if their connection points exist
48 for (int j = 0; j < PointCount; j++) {
49 if (PointsDesc[j][LineNumber] == 1)
50 {
51 boolean flag = true;
52 for (int k = 0; k < LeftCount; k++)
53 if (PointsDesc[j][LeftPoints[k]] == 0) {
54 flag = false;
55 break;
56 }
57 if (flag)
58 firstpoint = j;
59 }
60
61
62 if (PointsDesc[j][LineNumber] == 1) {
63 boolean flag = true;
64 for (int k = 0; k < RightCount; k++)
65 if (PointsDesc[j][RightPoints[k]] == 0) {
66 flag = false;
67 break;
68 }
69 if (flag)
70 secondpoint = j;
71 }
72 }
73
74 if (firstpoint == -1)
75 {
76 PointsDesc[PointCount][LineNumber] = 1;
77 for (int k = 0; k < LeftCount; k++)
78 PointsDesc[PointCount][LeftPoints[k]] = 1;
79 firstpoint = PointCount;
80 PointCount++;
81 }
82 if (secondpoint == -1)
83 {
84 PointsDesc[PointCount][LineNumber] = 1;
85 for (int k = 0; k < RightCount; k++)
86 PointsDesc[PointCount][RightPoints[k]] = 1;
87 secondpoint = PointCount;
88 PointCount++;
89 }
90
91 D[firstpoint][secondpoint] = LineLength;
92 D[secondpoint][firstpoint] = LineLength;
93 LineDesc[LineNumber][0] = firstpoint;
94 LineDesc[LineNumber][1] = secondpoint;
95 }
96
97 /* System.out.print(" ");
98 for (int i = 0; i < PointCount; i++) System.out.print(i + "\t");
99 System.out.println();
100
101 for (int i = 0; i < PointCount; i++) {
102 System.out.print(i + ": ");
103 for (int j = 0; j < PointCount; j++)
104 System.out.print(D[i][j] + "\t");
105 System.out.println();
106 }*/
107
108 /* for (int i = 0; i < PointCount; i++) {
109 System.out.print("a" + i + ": ");
110 for (int j = 1; j <= N; j++)
111 if (PointsDesc[i][j]!=0)
112 System.out.print(j + " ");
113 System.out.println();
114 }*/
115
116 int min = 1000000;
117 for (int l = 1; l <= N; l++)
118 {
119 int left = LineDesc[l][0];
120 int right = LineDesc[l][1];
121 int temp = D[left][right];
122 //System.out.print(left + "," + right + "\t");
123 D[left][right] = -1;
124 D[right][left] = -1;
125
126 int source = left;
127
128 int[] distance = new int[PointCount];
129 for (int i = 0; i < PointCount; i++)
130 if (D[source][i] != - 1)
131 distance[i] = D[source][i];
132 else
133 distance[i] = 1000000;
134
135 boolean[] visited = new boolean[PointCount];
136 int nodevisited = 1;
137 distance[source] = 0;
138 visited[source] = true;
139 while (nodevisited < PointCount) {
140 int mindis = 1000000;
141 int find = -1;
142 for (int k = 0; k < PointCount; k++)
143 if (visited[k] == false && k != source && distance[k] < mindis)
144 {
145 mindis = distance[k];
146 find = k;
147 }
148 if (find != -1) {
149 visited[find] = true;
150 distance[find] = mindis;
151 for (int k = 0; k < PointCount; k++)
152 if (D[find][k] != -1) {
153 if (distance[find] + D[find][k] < distance[k])
154 distance[k] = distance[find] + D[find][k];
155 }
156 }
157 nodevisited++;
158 }
159 /* for (int i = 0; i < PointCount; i++) System.out.print(distance[i] + " ");
160 System.out.println();*/
161 if (distance[right] + temp < min)
162 min = distance[right] + temp;
163
164 D[left][right] = temp;
165 D[right][left]= temp;
166 }
167 out.println(min);
168 out.close();
169 System.exit(0);
170 }
171 }
172
可惜BlogJava的著色不是很好看
USACO 4.1.1 Fence Loops
說一下大致的做法吧，算是結(jié)題報(bào)告，不過可能會被鄙視。
首先就是把圖轉(zhuǎn)化一下，因?yàn)轭}里面給的那種表達(dá)形式是沒辦法用任何關(guān)于點(diǎn)的圖的算法的。
我的轉(zhuǎn)化方法就是：
對于每條邊，最多在圖中添加兩個(gè)新的節(jié)點(diǎn)，這要取決于該節(jié)點(diǎn)是否與圖中的其他節(jié)點(diǎn)重合
打個(gè)比方來說，例子中的邊2，當(dāng)你添加這條邊的時(shí)候，你就只需要添加一個(gè)新的節(jié)點(diǎn)，因?yàn)檫@條變的一個(gè)節(jié)點(diǎn)跟邊1的一個(gè)節(jié)點(diǎn)重合了。
現(xiàn)在的問題就是，怎么來判斷要添加的節(jié)點(diǎn)跟現(xiàn)有的節(jié)點(diǎn)是否重合。
我們可以發(fā)現(xiàn)，如果兩個(gè)節(jié)點(diǎn)，他們所共有的邊是一樣的，那么這兩個(gè)節(jié)點(diǎn)肯定就是一個(gè)點(diǎn)。
比如，例子中的左上角第一個(gè)點(diǎn)，它的占有的邊的集合是（1，2，7）
當(dāng)你在處理邊2的時(shí)候，你會發(fā)現(xiàn)，它有一個(gè)端點(diǎn)鏈接的邊是（1，7），算上它自己，就也是（1，2，7)
于是，他們肯定是共享一個(gè)點(diǎn)的。
不知道說清楚了沒有
通過這個(gè)過程，就可以把輸入的圖轉(zhuǎn)化成為一個(gè)鄰接矩陣。
后來的算法我是看了NOCOW才知道的，剛開始想用Floyd直接算到自己的回路，發(fā)現(xiàn)不行，因?yàn)橐粭l邊可能被用兩次。那樣就不是一個(gè)封閉的圖形了。
NOCOW上的辦法就是，一次去掉一個(gè)邊，然后算這條邊兩邊節(jié)點(diǎn)的最短路
如果存在的話，結(jié)果再加上這條邊的長度，那么就是這個(gè)封閉圖的周長。
總共算N次，由于途中的節(jié)點(diǎn)最多最多也只能有N + 1個(gè)，就是一個(gè)接著一個(gè)，連成一個(gè)環(huán)的情況。
所以算法的復(fù)雜度應(yīng)該是O（N^3)，還不是很壞。
我沒做什么剪枝，用JAVA寫的，也直接過了。
中間Dij算法寫錯(cuò)了N次，現(xiàn)在想想，以前寫的可能也得是錯(cuò)的，但是都沒有被找出毛病來。