USACO Training Section 2.3 Controlling company

英文原题  中文题译

大意：公司之间相互持有股份，如果A有B的51%以上的股份，则控股B，如果A控股B1,....Bk，这些公司和A本身对公司C的股份之和在51%以上，则A也控股C。给定公司间的股份持有率，要求计算公司之间的控股关系。

控股关系看上去很像偏序关系，不过不是。但其类似的传递性吸引人往Watshell算法上去考虑。于是有了第一个版本的程序。注意到一次watshell是不足以计算出控股关系的，需要多次计算。

此题中的陷阱：通常我们会在计算传递关系时将股份直接相加，但在极端情况下，100个公司的数据就足以使得32位整数溢出。这看起来觉得很荒唐，但的确发生了。一个环形控股实例（官方测试数据９）上就能发现。但这个错相当隐蔽，我看到NOCOW上似乎没人提到这一点，把能否通过归结成所谓RP。看下面第一实现的35行，第二个实现的40行，就是用来控制溢出的。如果没有这个，就需要在迭代或者循环中保存局部数据，做批次处理。（事实上我的第一个通过的版本就是这样做的，在不清楚溢出导致问题的情况下，保守的采取同步扩展的策略）。

/*
ID: blackco3
TASK: concom
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
#define _max_ 100
#define max(x,y) ((x)>(y)?(x):(y))

int main() {
	freopen("concom.in", "r", stdin);
	freopen("concom.out", "w", stdout);	
	int n_triple, n_comp=0, rate[_max_][_max_];
	cin >> n_triple ;
	memset( rate, 0, sizeof(rate) );
	for( int i=0; i<n_triple; i++ ){
		int a, b ;
		cin >> a >> b ;
		cin >> rate[a-1][b-1] ;
		n_comp= max(n_comp, max(a,b)); 
	}

	int expanded[_max_][_max_], expanding ;
	memset( expanded, 0, sizeof(expanded) );
	do {
		expanding=0 ;
		for( int i=0; i<n_comp; i++ ){
			for( int k=0; k<n_comp; k++ ){		
				if( rate[i][k]<=50 || expanded[i][k] )
					continue ;
				expanded[i][k]=1 , expanding=1;
				for( int j=0; j<n_comp; j++ ) 
					rate[i][j] = min(rate[k][j]+rate[i][j], 100) ;
			}
		}
	}while(expanding);
	for( int i=0; i<n_comp; i++ )
		for( int j=0; j<n_comp; j++ ){
			if( i==j || rate[i][j]<50 )
				continue ;
			cout << i+1 << " " << j+1 << endl ;
		}
	return 0;
}

上述版本的扩展队列实现，其基本过程完全一致，但体现从不同角度来考虑这个问题。写前面的代码基本上是从Watshell开始考虑的，写这个代码的基本上是直接考虑暴力求解的。注意到一个典型差别，在前者中有一个expanded数组来控制重复访问，而在后者中似乎没有。事实上后者用从不大于50到超过50的控股率来做标志，每个公司对只会产生一次这样的转换，因而不需要额外的判断重复的代码。

但一开始（没有40行对数据溢出的控制）还是出问题，在测试数据9下程序越界崩溃，百思不得其解，最终想到这个越界问题。看起来似乎100次加100肯定不越界，但事实上，如第一次有n个是200, 第二次产生400，....越界几乎是必然的！

这两个算法的对比满有意思，我们可以从第二个算法中提取出一个计算传递闭包的新算法来。另文描述。

/*
ID: blackco3
TASK: concom
LANG: C++
*/
#include <iostream>
#include <stdlib.h>
#include <memory.h>
using namespace std;
#define _max_ 110
#define max(x,y) ((x)>(y)?(x):(y))
struct t_ctrl {
	int parent, son ;
} ctrl_list[_max_*_max_], *p_tail=ctrl_list;
int ctrl_comp( const void *c1, const void *c2 ) {
	return ((t_ctrl*)c1)->parent==((t_ctrl*)c2)->parent ?  
		((t_ctrl*)c1)->son-((t_ctrl*)c2)->son : ((t_ctrl*)c1)->parent-((t_ctrl*)c2)->parent ;
} 

int main() {
	freopen("concom.in", "r", stdin);
	freopen("concom.out", "w", stdout);	
	int n_triple, n_comp=0, rate[_max_][_max_] ;
	cin >> n_triple ;
	memset( rate, 0, sizeof(rate) );
	for( int i=0; i<n_triple; i++ ){
		int a, b ;
		cin >> a >> b ;
		n_comp= max(n_comp, max(a,b)); 
		cin >> rate[--a][--b] ;
		if( rate[a][b] > 50 )
			p_tail->parent=a , p_tail->son=b, p_tail++ ;
	}
	int counter=0, next;
	for( t_ctrl *pc=ctrl_list; pc!=p_tail; pc++ ){
		for( int j=0; j<n_comp; j++ ) { 
			next = rate[pc->parent][j] + rate[pc->son][j] ;
			if( rate[pc->parent][j]<=50 && next>50 )
				p_tail->parent=pc->parent , p_tail->son=j, p_tail++ , counter++;
			rate[pc->parent][j] = next>100? 100 : next ;
		}
	}
	qsort( ctrl_list, p_tail-ctrl_list, sizeof(t_ctrl), ctrl_comp );
	for( t_ctrl *pc=ctrl_list; pc!=p_tail; pc++ )
		if( pc->parent != pc->son )
		cout << pc->parent+1 << " " << pc->son+1 << endl ;
	return 0;
}