The fences that surround Farmer Brown's collection of pastures have gotten out of control. They are made up of straight segments from 1 through 200 feet long that join together only at their endpoints though sometimes more than two fences join together at a given endpoint. The result is a web of fences enclosing his pastures. Farmer Brown wants to start to straighten things out. In particular, he wants to know which of the pastures has the smallest perimeter.
Farmer Brown has numbered his fence segments from 1 to N (N = the total number of segments). He knows the following about each fence segment:
-
the length of the segmentthe segments which connect to it at one endthe segments which connect to it at the other end. Happily, no fence connects to itself.
Given a list of fence segments that represents a set of surrounded pastures, write a program to compute the smallest perimeter of any pasture. As an example, consider a pasture arrangement, with fences numbered 1 to 10 that looks like this one (the numbers are fence ID numbers):
1
+---------------+
|\ /|
2| \7 / |
| \ / |
+---+ / |6
| 8 \ /10 |
3| \9 / |
| \ / |
+-------+-------+
4 5
The pasture with the smallest perimeter is the one that is enclosed by fence segments 2, 7, and 8.
PROGRAM NAME: fence6
INPUT FORMAT
| Line 1: | N (1 <= N <= 100) |
| Line 2..3*N+1: | N sets of three line records: The first line of each record contains four integers: s, the segment number (1 <= s <= N); Ls, the length of the segment (1 <= Ls <= 255); N1s (1 <= N1s <= 8) the number of items on the subsequent line; and N2sthe number of items on the line after that (1 <= N2s <= 8).The second line of the record contains N1 integers, each representing a connected line segment on one end of the fence.The third line of the record contains N2 integers, each representing a connected line segment on the other end of the fence. |
OUTPUT FORMAT
The output file should contain a single line with a single integer that represents the shortest surrounded perimeter.这道题可以看出是求最小环。因为n的范围很小，可以采用如下方法：
①floyd求最小环（更推荐这个，因为代码简洁）
②用最短路的dijskra算法或是SPFA算法，每次删掉一条边求最短路，如果从左侧顶点到右侧定点仍存在最短路，那么加上这条边后，就是一个最小环了。同时更新答案。
但是我想说，这两种方法都不好O(∩_∩)O~~
因为读入的是边集而不是我们日常做的点集，所以在转化的过程中会比较麻烦。推荐用DFS直接0ms秒过。
代码：
/* ID:juan1973 LANG:C++ PROG:fence6 */ #include#include using namespace std; const int maxn=101; int num[maxn][2],map[maxn][2][10],f[maxn],n,i,ans,start,c,j; bool flag[maxn]; int find(int a,int b) { for (int i=1;i<=num[b][0];i++) if (map[b][0][i]==a) return 0; return 1; } void dfs(int k,int d,int s) { if (s>ans) return; if (k==start&&s>0) {ans=s;return;} flag[k]=true; for (int i=1;i<=num[k][d];i++) { int go=map[k][d][i]; if (!flag[go]||go==start) dfs(go,1-find(k,go),s+f[k]); } flag[k]=false; } int main() { freopen("fence6.in","r",stdin); freopen("fence6.out","w",stdout); scanf("%ld",&n); for (i=1;i<=n;i++) { scanf("%ld",&c); scanf("%ld%ld%ld",&f[c],&num[c][0],&num[c][1]); for (j=1;j<=num[c][0];j++) scanf("%ld",&map[c][0][j]); for (j=1;j<=num[c][1];j++) scanf("%ld",&map[c][1][j]); } ans=9999999; for (start=1;start<=n;start++) { memset(flag,0,sizeof(flag)); dfs(start,0,0); } printf("%ld\n",ans); return 0; } //果断放弃一下转化代码。
/*for (i=1;i<=n;i++)
scanf("%ld%ld%ld%ld",&p[i],&map_e[i],&map[0][p[i]][0],map[1][p[i]][0]);
for (j=1;j<=map[0][p[i]][0];j++) scanf("%ld",&map[0][p[i]][j]);
for (j=1;j<=map[1][p[i]][0];j++) scanf("%ld",&map[1][p[i]][j]);
}
flag[0][1]=true;now_e=1;now_v;cnt=1;
while (true)
{
for (i=1;i<=n;i++)
{
find=false;
for (j=0;j<=1;j++)
for (k=1;k<=map[j][i][0];k++)
if (map[j][i][k]==now_e)*/