johnson算法.cpp

自己编写的

#include <iostream>
#include <ctime>
#include <set>
const int N = 201;
int p[100];
int min = 65535;
using  namespace std;

int main()
{
	int n;         // 字句的个数
	scanf("%d",&n);
	int a[N][3];
	int i,j,k = 0;
	int t1,t2,t3;
	set<int> variab; // 用来存储变元
	set<int>::iterator iter;
	for(i = 0; i < n; i++){
		scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
		t1 = abs(a[i][0]);
		iter = variab.find(t1);
		if(iter == variab.end())
			variab.insert(t1);

		t2 = abs(a[i][1]);
		iter = variab.find(t2);
		if(iter == variab.end())
			variab.insert(t2);

		t3 = abs(a[i][2]);
		iter = variab.find(t3);
		if(iter == variab.end())
			variab.insert(t3);
	}
	int t = 10,count,temp;
	while(t--){
		count = 0;
		time_t timer;
		srand((unsigned)time(&timer));
		for(iter = variab.begin(); iter != variab.end(); iter++){
			temp = *iter;
			p[temp] = rand() % 2;     // 产生0-1之间随机数
		}
		for(i = 0; i < n; i++){
				if((a[i][0]>0&&(p[a[i][0]]==1))||(a[i][0]<0&&(p[abs(a[i][0])]==0))){
					count++;
					continue;
				}
				if((a[i][1]>0&&(p[a[i][1]]==1))||(a[i][1]<0&&(p[abs(a[i][1])]==0))){
					count++;
					continue;
				}
				if((a[i][2]>0&&(p[a[i][2]]==1))||(a[i][2]<0&&(p[abs(a[i][2])]==0))){
					count++;
				}
		}
		if(count < min)
			min = count;
	}
	printf("%d\n",min);


	return 0;
}