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
说一下大致的做法吧，算是结题报告，不过可能会被鄙视。
首先就是把图转化一下，因为题里面给的那种表达形式是没办法用任何关于点的图的算法的。
我的转化方法就是：
对于每条边，最多在图中添加两个新的节点，这要取决于该节点是否与图中的其他节点重合
打个比方来说，例子中的边2，当你添加这条边的时候，你就只需要添加一个新的节点，因为这条变的一个节点跟边1的一个节点重合了。
现在的问题就是，怎么来判断要添加的节点跟现有的节点是否重合。
我们可以发现，如果两个节点，他们所共有的边是一样的，那么这两个节点肯定就是一个点。
比如，例子中的左上角第一个点，它的占有的边的集合是（1，2，7）
当你在处理边2的时候，你会发现，它有一个端点链接的边是（1，7），算上它自己，就也是（1，2，7)
于是，他们肯定是共享一个点的。
不知道说清楚了没有
通过这个过程，就可以把输入的图转化成为一个邻接矩阵。
后来的算法我是看了NOCOW才知道的，刚开始想用Floyd直接算到自己的回路，发现不行，因为一条边可能被用两次。那样就不是一个封闭的图形了。
NOCOW上的办法就是，一次去掉一个边，然后算这条边两边节点的最短路
如果存在的话，结果再加上这条边的长度，那么就是这个封闭图的周长。
总共算N次，由于途中的节点最多最多也只能有N + 1个，就是一个接着一个，连成一个环的情况。
所以算法的复杂度应该是O（N^3)，还不是很坏。
我没做什么剪枝，用JAVA写的，也直接过了。
中间Dij算法写错了N次，现在想想，以前写的可能也得是错的，但是都没有被找出毛病来。