center.c

赋权有向图中心问题 问题描述: 设G=(V,E)是一个赋权有向图

#include <stdio.h >
#include <malloc.h>
int main()
{
	int i,j,k,u,v,w,n,m,t1,t2,t3,center,dis;
	int **a;
	int **c;
	int *max;
	freopen ("input.txt","r",stdin);
	freopen ("output.txt","w",stdout);
	scanf ("%d%d",&n,&m);
	a=(int**)malloc((n+1)*sizeof(int*));         	//定义动态数组	
		for (i=1;i<=n;i++) 
			a[i]=(int *)malloc((n+1)*sizeof(int));
		c=(int**)malloc((n+1)*sizeof(int*));
		for (i=1;i<=n;i++) 
			c[i]=(int *)malloc((n+1)*sizeof(int));
		max=(int*)malloc((n+1)*sizeof(int));
		for (i=1;i<=n;i++)
			max[i]=0;     //初始化max
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				a[i][j]=32768;   //初始化a 
			for (i=1;i<=m;i++){
				scanf("%d%d%d\n",&u,&v,&w);
				a[u][v]=w;
			}
			for (i=1;i<=n;i++)          //求出所有顶点对的最短距离
				for (j=1;j<=n;j++){
					c[i][j]=a[i][j];
				}
				for (i=1;i<=n;i++)
					c[i][i]=0;
				for (k=1;k<=n;k++)
					for (i=1;i<=n;i++)
						for (j=1;j<=n;j++){
							t1=c[i][k];
							t2=c[k][j];
							t3=c[i][j];
							if (t1!=32768&&t2!=32768&&(t3==32768||t1+t2<t3))
								c[i][j]=t1+t2;
						}
						for (j=1;j<=n;j++)      //求所有顶点的偏心距
							for (i=1;i<=n;i++)
								if((c[i][j]>max[j])&&(c[i][j]!=32768))
									max[j]=c[i][j];
								dis=32768; center=0;      //找出最小的偏心距
								for (i=1;i<=n;i++)
									if (max[i]<dis&&max[i]!=0)
									{
										dis=max[i];
										center=i;
									}
									printf ("%d\n%d",dis,center);
	return 0;
}