3216.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <memory.h>

int dis[30][30];
int n, m;
int p[210], t[210], d[210];

#define null 0
const int size = 210;
bool w[size][size];

//size must be bigger than n and m.
//n小于m时效率高
int maxmatch( int n, int m, bool w[][size], int *p)
{

	int p_n[size];
	int p_m[size];

	bool sign[size];
	int q[size],from[size],s,t;

	int i,j,link,now,h;

	memset( p_n, -1, sizeof(int)*n );
	memset( p_m, -1, sizeof(int)*m );

	for(i=0;i<n;i++)
	if(p_n[i]==-1)
	{
		memset( sign, 0, sizeof(bool)*m );
                
		s=1;link=-1;
		from[0]=-1;

		q[0]=size-1;
		p_m[size-1]=i;

		for(t=0;t<s;t++)
		{
		   now=q[t];
		   for(j=0;j<m;j++)
		   {
			   if( w[p_m[now]][j] != null && sign[j]==0 )
			   {
					sign[j]=1;
					q[s]=j;
					from[s++]=t;

					if(p_m[j]==-1)
					{
						link=s-1;
						break;
					}
			   }
		   }
		   if(j<m)break;
		}

		if(t<s)
		{
			 while(from[link]!=-1)
			 {
					h=from[link];
					p_m[q[link]]=p_m[q[h]];
					p_n[p_m[q[h]]]=q[link];
					link=h;
			 }
		}

		//无完备匹配
		//else return 0;
	}
	int an;

	for(i=0,an=0;i<n;i++)
	{
		if(p)p[i]=p_n[i];
		if(p_n[i]>=0)an++;
	}
	return an;
}

bool input( ) {
	int i, j, k;

	scanf( "%d%d", &n, &m );

	if( n == 0 && m == 0 )
		return false;

	for( i=0; i<n; i++ )
	for( j=0; j<n; j++ )
		scanf( "%d", &dis[i][j] );

	for( k=0; k<n; k++ )
	for( i=0; i<n; i++ )
	for( j=0; j<n; j++ )
		if( dis[i][k] >= 0 && dis[k][j] >= 0 && 
				( dis[i][j]<0 || dis[i][k]+dis[k][j]<dis[i][j] ) )
				dis[i][j] = dis[i][k]+dis[k][j];
	
	for( i=0; i<m; i++ ) {
		scanf( "%d%d%d", p+i, t+i, d+i );
		p[i]--;
	}
	return true;
}


int main( ) {
	int i, j;
	while( input() ) {
		memset( w, 0, sizeof w );
		for( i=0; i<m; i++ )
		for( j=0; j<m; j++ )
			if( i != j )
				if( dis[p[i]][p[j]] >= 0 && 
					t[i] + d[i] + dis[p[i]][p[j]] <= t[j] )
					w[i][j] = true;
		printf( "%d\n", m-maxmatch( m, m, w, 0 ) );
	}
	return 0;
}