task.cpp

该程序用于计算任务分配问题

#include<iostream.h>
long cost=100;
void swap(int &a,int &b)
{
	int temp=a;
	a=b;
	b=temp;
}

void perm(int **link,int *list,int *a,int k,int n)
{
	if(k==n)
	{
		long num=0;
		for(int i=1;i<=n;i++)
			num+=link[i][list[i]];
		if(num<cost)
		{
			cost=num;
			for(i=1;i<=n;i++)
				a[i]=list[i];
		}
	}
	else
		for(int i=k;i<=n;i++)
		{
			swap(list[k],list[i]);
			perm(link,list,a,k+1,n);
			swap(list[k],list[i]);
		}
}

void main()
{
	int n,i,j;
	cout<<"输入任务的数目"<<endl;
	cin>>n;
	int **link,*list,*a;
	link=new int *[n+1];
	for(i=1;i<=n;i++)
		link[i]=new int[n+1];
	list=new int[n+1];
	a=new int[n+1];
	for(i=1;i<=n;i++)
		list[i]=i;
	cout<<"输入每个人做各件事的时间"<<endl;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			cin>>link[i][j];
    perm(link,list,a,1,n);
	cout<<"最短时间: "<<cost<<endl;
	cout<<"人与事件的对应:"<<endl;
	for(i=1;i<=n;i++)
		cout<<i<<"----"<<a[i]<<endl;
}