USACO Training Section 4.1 Fence Loops

英文原题

 

大意：

 

农夫布朗的牧场上的篱笆已经失去控制了。它们分成了1~200英尺长的线段。只有在线段的端点处才能连接两个线段，有时给定的一个端点上会有两个以上的篱笆。结果篱笆形成了一张网分割了布朗的牧场。布朗想将牧场恢复原样，出于这个考虑，他首先得知道牧场上哪一块区域的周长最小。

布朗将他的每段篱笆从1到N进行了标号（N=线段的总数）。他知道每段篱笆的有如下属性：

• 该段篱笆的长度
• 该段篱笆的一端所连接的另一段篱笆的标号
• 该段篱笆的另一端所连接的另一段篱笆的标号

幸运的是，没有篱笆连接它自身。对于一组有关篱笆如何分割牧场的数据，写一个程序来计算出所有分割出的区域中最小的周长。

 

           1
   +---------------+
   |\             /|
  2| \7          / |
   |  \         /  |
   +---+       /   |6
   | 8  \     /10  |
  3|     \9  /     |
   |      \ /      |
   +-------+-------+
       4       5

分析与实现

 

原题给出的是图的对偶图，能在不复原原图的情况下求得环路吗？一开始想到在深度优先搜索中任意到已访问过的边都构成环路，就想当然的实现了。结果测试发现不对。于是实现了将对偶图复原成原图在顶点图上同样的算法，依然不正确。才想起来反省思路是否正确。的确不对，即使是对每个顶点都做一次深搜，也不能保证得到最小环，原因：有的环需要多于1条回边。因此，从设计思路来说，这样想，无法得到正确的结果。

 

于是换个角度考虑，既然已经得到了原图，那么，每次将一个顶点按其邻接边拆分成对应的不相邻顶点，这些顶点之间的最短路径，即为原图中的环。考虑到这个图本身稀疏的，用Bellman_Ford_SPFA对新生成的顶点各执行一次即可。这样，算法的总复杂度为DE，D为顶度数之和，E为边数。可以接受。

实现时注意两点：

1. 从对偶图得到正确的原图。这需要两次扫描。

2. 如何用最小的代价构造新图。不需要拷贝，只需要修改涉及的边，并在邻接表缓存的尾部增加相应的边即可。

 

/*
ID: blackco3
TASK: fence6
LANG: C++
*/
#include <iostream> 
#include <memory.h>
using namespace std;
const int _max_path_(200), _max_vex_(_max_path_<<1), _max_int_(0x7fffffff); 
struct t_path{
	int dis, v[2], n_adj[2], adj[2][_max_path_] ;
} pathes[_max_path_+1] ;
struct t_adj {
	int to, dis ;
	t_adj( int t=0, int d=0 ) : to(t), dis(d) {} ;
} adj_buf[_max_path_<<1], *p_adj_end ;
struct t_vex {
	int n_adj ;
	t_adj *adj ;
} vexes[_max_vex_];
int n_path(0), n_vex(0) ;

int sdis[_max_vex_], queue[_max_vex_], in_que[_max_vex_] ;
void Bellman_Ford_SPFA( int source, int n_add_on ){
	memset( sdis, 0x7f, sizeof(int)*(n_vex+n_add_on) );
	memset( in_que, 0, sizeof(int)*(n_vex+n_add_on) ) ;
	int *head=queue, *tail=queue; 
	sdis[source]=0 , in_que[source]=1, *(tail++)=source ;
	do{
		register int cvex= *head ;
		in_que[cvex]=0, head = (head-queue)==_max_vex_-1 ? queue : head+1;
		for( t_adj *p_adj=vexes[cvex].adj; p_adj!=vexes[cvex].adj+vexes[cvex].n_adj; p_adj++ ){
			if( p_adj->dis + sdis[cvex] >= sdis[p_adj->to] )
				continue ;
			sdis[p_adj->to] = p_adj->dis + sdis[cvex] ;
			if( !in_que[p_adj->to] ){
				*tail=p_adj->to , in_que[p_adj->to]=1 ;
				tail = (tail-queue)==_max_vex_-1 ? queue : tail+1;
			}
		}
	}while( head!=tail );
}

void build_graph( ){
	memset( vexes, 0, sizeof(t_vex)*n_vex ) ;
	for( t_path *pc=pathes+1; pc!=pathes+n_path+1; pc++ ){
		vexes[pc->v[0]].n_adj++, vexes[pc->v[1]].n_adj++ ;
		printf("Edge %d : <%d,%d> \n", pc-pathes, pc->v[0], pc->v[1]) ;
	}

	t_adj *p_adj=adj_buf;
	for( int i=0; i<n_vex; i++ )
		vexes[i].adj=p_adj, p_adj+=vexes[i].n_adj, vexes[i].n_adj=0 ;
	p_adj_end = p_adj ;
	
	for( t_path *pc=pathes+1; pc!=pathes+n_path+1; pc++ ){
		int v1=pc->v[0], v2=pc->v[1], dis=pc->dis ;
		vexes[v1].adj[ vexes[v1].n_adj++ ]=t_adj(v2,dis);
		vexes[v2].adj[ vexes[v2].n_adj++ ]=t_adj(v1,dis);
	}
}

void analysis_path( ) {
    cin >> n_path ;
	for( int i=0; i<n_path; i++){
		int id ;
		cin >> id ;
		cin >> pathes[id].dis >> pathes[id].n_adj[0] >> pathes[id].n_adj[1] ;
		for( int j=0; j < pathes[id].n_adj[0] ; j++ )
			cin >> pathes[id].adj[0][j] ;
		for( int j=0; j < pathes[id].n_adj[1] ; j++ )
			cin >> pathes[id].adj[1][j] ;
		pathes[id].v[0] = pathes[id].v[1] = -1 ;
	}
	for( int ie=1; ie<=n_path; ie++ ){
		for( int in=0; in<2; in++ ){
			if( pathes[ie].v[in]!=-1 )
				continue ;
			pathes[ie].v[in] = n_vex ;
			for( int ic=0; ic<pathes[ie].n_adj[in]; ic++ ){
				int ie_con = pathes[ie].adj[in][ic], found = 0 ;
				for( int iadj=0; iadj<pathes[ie_con].n_adj[0]; iadj++ ){
					if( pathes[ie_con].adj[0][iadj]==ie ){
						found = 1, pathes[ie_con].v[0] = n_vex ;
						break ;
					}
				if( !found )
					pathes[ie_con].v[1] = n_vex ;
				}
			}
			n_vex++ ;
		}
	}
}

void show_graph( int more=0 ){
	for( int i=0; i<n_vex+more; i++ ){
		printf("[%d]ADJ %d : ", i, vexes[i].n_adj);
		for( int j=0; j<vexes[i].n_adj; j++ )
			printf("%d[%d] ", vexes[i].adj[j].to, vexes[i].adj[j].dis );
		printf("\n");
	}
	printf("-------------------------------------------------------------\n");

}

int min_peri=_max_int_ ;
void count_special( int vex ){
	if( vexes[vex].n_adj==1 )
		return ;

	memcpy( p_adj_end, vexes[vex].adj, sizeof(t_adj)*vexes[vex].n_adj ); 
	t_vex *p_add = vexes + n_vex ;
	for( int i=0; i<vexes[vex].n_adj; i++ ){
		int to = vexes[vex].adj[i].to ;
		for( int j=0; j<vexes[to].n_adj; j++ )
			if( vexes[to].adj[j].to == vex ) {
				vexes[to].adj[j].to = n_vex + i ; 
				break ;
			}
		p_add->adj = p_adj_end+i , p_add->n_adj=1, p_add++ ; 
	}
	show_graph( vexes[vex].n_adj ); 

	for( int i=0; i<vexes[vex].n_adj; i++ ){
		Bellman_Ford_SPFA( n_vex + i , vexes[vex].n_adj );
		for( int j=0; j<vexes[vex].n_adj; j++ )
			if( i!=j && sdis[ n_vex+i ] < min_peri )
				min_peri = sdis[ n_vex+j ] ;
	}

	for( int i=0; i<vexes[vex].n_adj; i++ ){
		int to = vexes[vex].adj[i].to ;
		for( int j=0; j<vexes[to].n_adj; j++ )
			if( vexes[to].adj[j].to >= n_vex ) {
				vexes[to].adj[j].to = vex ; 
				break ;
			}
	}
	show_graph( );

}

int main() {
    freopen("fence6.in", "r", stdin); 
    //freopen("fence6.out","w",stdout);

	analysis_path( ) ;
	build_graph( ) ;
	show_graph();
	for( int i=0; i<n_vex; i++ )
		count_special(i);
	cout << min_peri << endl ;
	return 0; 
} 

 

 

附：对偶图上的边搜索环构造算法。