Algorithm

USACO Section4.1 fence6

Problem Summary

Given a graph, find the minimum length cycle.

Analysis & Solution

We can enumerate the edges, and use DFS to search for the answer. To do this, we need to mark the directions of the edges. But this method saves us the trouble of reperesenting the graph with vertices.

Solution 2 : Modified shortest path algorithm

Step 1 : Graph Representation

Let the endpoints be the vertices of the graph, and the distance between two endpoints of an edge be the length of the edge. Then connect the vertices that are at the same location. Now, we have a graph reprensented with an adjacency matrix.

Step 2: Find the minimum length cycle

  1. Dijkstra :
    We enumerate edges. For each edge, we delete it from the graph, and use Dijkstra algorithm to find the distance between its two endpoints, then add it with the length of this edge. The sum is the miminum length of cycles including this edge. So, the minimum of the sums is the answer.

  2. Modified Floyd :

Define g[i][j] as the initial distance of i and j, and dist[i][j] as the minimal distance between i and j.

Notice that, at the start of the kth time of the outermost loop in Floyd algorithm, the value of dist[i][j] is the minimum of distance between vertice i and vertice j via vertices whose number is less than k.

Then we consider the cycles including vertex k, and other vertices in it have vertex numbers less than k, i.e. 1,2,…,k-1. Let us enumerate the two vertices adjacent to vertex k in the cycle, and mark them as i and j, then the length of the cycle is g[k][i]+dist[i][j]+g[j][k].

Obviously, the positive minimal value of g[k][i]+dist[i][j]+g[j][k] (i!=j, i<k, j<k) is the answer.

Code

Code of Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
using namespace std;
const int maxn = 102;
int n,ans;
int v[maxn][2][10],len[maxn];
bool dir[maxn][maxn],vis[maxn];
void dfs(int cur,int d,int sum,int s)
{
	if(sum>=ans) return;
	vis[cur]=true;
	for(int i=1;i<=v[cur][1-d][0];i++)
	{
		int t=v[cur][1-d][i];
		int out=dir[t][cur];
		if(t==s && out==0)
		{
			ans=sum<ans ? sum:ans;
			return;
		}
		if(vis[t]) continue;
		vis[t]=true;
		dfs(t,out,sum+len[t],s);
		vis[t]=false;
	}
}
int main()
{
	fstream fin("fence6.in",ios::in);
	fstream fout("fence6.out",ios::out);
	fin>>n;
	int s;
	for(int i=0;i<n;i++)
	{
		fin>>s;
		fin>>len[s];
		fin>>v[s][0][0]>>v[s][1][0];
		for(int j=1;j<=v[s][0][0];j++)
			fin>>v[s][0][j];
		
		for(int j=1;j<=v[s][1][0];j++)
		{
			fin>>v[s][1][j];
			dir[s][v[s][1][j]]=true;
		}
	}
	
	ans=INT_MAX;
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		dfs(i,0,len[i],i);
	}
	
	fout<<ans<<endl;
	fin.close();
	fout.close();
	return 0;
}

Code of Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int maxn = 102;
const int maxm = 202;
const int maxd = 30000;
int n,m;
int v[maxn][2][10],len[maxn];
int g[maxm][maxm],dist[maxm][maxm];
int main()
{
	fstream fin("fence6.in",ios::in);
	fstream fout("fence6.out",ios::out);
	fin>>n;
	m=n<<1;
	for(int i=1;i<m;i++)
		for(int j=i+1;j<=m;j++)
			g[i][j]=g[j][i]=maxd;
	for(int i=0;i<n;i++)
	{
		int s;
		fin>>s;
		fin>>len[s];
		int a = s<<1;
		int b = a-1;
		g[a][b]=g[b][a]=len[s];
		fin>>v[s][0][0]>>v[s][1][0];
		for(int j=1;j<=v[s][0][0];j++)
			fin>>v[s][0][j];
		
		for(int j=1;j<=v[s][1][0];j++)
			fin>>v[s][1][j];
	}
	for(int i=1;i<=n;i++)
		for(int k=0;k<=1;k++)
		{
			int s = (i<<1)-1+k ,t;
			int sum = v[i][k][0];
			for(int j=1;j<=sum;j++)
			{
				int cur = v[i][k][j];
				bool flag=false;
				for(int p=1;p<=v[cur][0][0];p++)
					if(v[cur][0][p]==i)
					{
						flag=true;
						break;
					}
				if(flag) t=(cur<<1)-1;
				else t=cur<<1;
				g[s][t]=g[t][s]=0;
			}
		}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			dist[i][j]=g[i][j];
	
	int ans=maxd;
	for(int k=1;k<=m;k++)
	{
		for(int i=1;i<k-1;i++)
			for(int j=i+1;j<k;j++)
			{
				int tmp = g[k][i]+dist[i][j]+g[j][k];
				if(tmp==0) continue;
				ans=tmp<ans ? tmp:ans;
			}
		for(int i=1;i<=m;i++)
			if(i!=k)
				for(int j=1;j<=m;j++)
					if(j!=i && j!=k)
					{
						int tmp = dist[i][k]+dist[k][j];
						dist[i][j]=tmp<dist[i][j] ? tmp:dist[i][j];
					}
	}
	
	fout<<ans<<endl;
	fin.close();
	fout.close();
	return 0;
}