usaco_4_1_3_fence6_求最小环.cpp

usaco自己做的1到5章的代码

/*
PROB: fence6
LANG: C++
*/
/*
这道题本意是算最小环，不过由于构图比较麻烦，所以我用深搜做了。
最小环的算法一般是最短路径的算法，用dijkstra算一对点的距离，加上边长就是一个环，找出其中最小的。
另外也有Floyd算法：
朴素算法
令e(u,v)表示u和v之间的连边，再令min(u,v)表示，删除u和v之间的连边之后，u和v之间的最短路
最小环则是min(u,v) + e(u,v)。时间复杂度是EV2。


改进算法
在floyd的同时，顺便算出最小环

g[i][j]=i,j之间的边长
dist:=g;
for k:=1 to n do
begin
     for i:=1 to k-1 do
         for j:=i+1 to k-1 do
             answer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);
     for i:=1 to n do
         for j:=1 to n do
             dist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);
end;

最小环改进算法的证明
一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,所有结点编号都小于k的最短路径长度。根据floyd的原理，在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径
综上所述，该算法一定能找到图中最小环。
*/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<fstream>
#include<string>
#include<queue>
#define cin fin
using namespace std;
ifstream fin("fence6.in");
ofstream fout("fence6.out");

int map[101][2][9];
int len[101];
int dis[101];
bool used[101][2];
int m=9999999,n,pt,now,dnow;

void dfs(int p,int d)
{
	int i,j;
	if(p==now && d==dnow)
	{
		if(used[0][0]) used[0][0]=false;
		else {if(m>pt) m=pt;
		return;}
	}
	if(pt>m) return;
	for(i=1;i<=map[p][d][0];i++)
	{
		int k=map[p][d][i];
		for(j=1;j<=map[k][0][0];j++) if(map[k][0][j]==p) break;
		if(j>map[k][0][0]) {
			if(!used[k][0]) {
				pt+=len[k];				
				used[k][0]=true;
				dfs(k,0);
				pt-=len[k];				
				used[k][0]=false;
			}
		}
		else if(!used[k][1])
		{
				pt+=len[k];				
				used[k][1]=true;
				dfs(k,1);
				pt-=len[k];				
				used[k][1]=false;
		}
		
	}
}
int main()
{
	int i,j,k,s,n1,n2;
	cin>>n;
	for(i=0;i<n;i++)
	{		
		cin>>j;
		cin>>len[j]>>map[j][0][0]>>map[j][1][0];
		for(k=1;k<=map[j][0][0];k++)
			cin>>map[j][0][k];
		for(k=1;k<=map[j][1][0];k++)
			cin>>map[j][1][k];
	}
	memset(used,false,sizeof(used));
	for(i=1;i<=n;i++)
	{
		pt=0;
		now=i;
		dnow=0;
		used[0][0]=true;
		dfs(now,0);
		pt=0;
		dnow=1;
		used[0][0]=true;
		dfs(now,1);
	}
	fout<<m<<endl;
	return 0;
}