#include<iostream>
#define n 501
#define INF 0x7fffffff
using namespace std;
int visy[n];
int conny[n];
int mat[n][n];

int len[n][n];
int dig[n][n];
int dis[n];
int num,l;
	int fang[n];
	int duilie[500000];

struct ok
{
	int bl;
	int st,re;
}s[n];
bool find(int t)
{
	int i;
	for(i=1;i<=num;i++)
	{
		if(visy[i]==0&&mat[t][i]==1)
		{
			visy[i]=1;
			if(conny[i]==-1||find(conny[i]))
			{
				conny[i]=t;
				return true;
			}
		}
	}
	return false;
}
void spfa (int t)
{
	int i;
	memset(duilie,0,sizeof(duilie));
	memset(fang,0,sizeof(fang));
	dis[t]=0;
	int head,tail;
	head=0;
	tail=0;
	duilie[tail++]=t;
	fang[t]=1;//1 biao si zai duilie
	while(head<tail)
	{
		int temp=duilie[head++];
		fang[temp]=0;
		
		for(i=1;i<=l;i++)
		{
			if(i==temp) continue;
			if((dis[temp]-dis[i])<dig[temp][i])
				{
					dis[i]=dis[temp]+dig[temp][i];
					if(fang[i]==0) 
				 {
					 duilie[tail++]=i;
					 fang[i]=1;
			     }
					 
			}
			  
		}
	}
}


	

int main()
{
	int i,j
		,k,tot;
	while(scanf("%d%d",&l,&num)==2)
	{
		if(l==0) break;
		for(i=1;i<=l;i++)
		{
			for(j=1;j<=l;j++)
			{
				scanf("%d",&dig[i][j]);
				if(dig[i][j]==-1) dig[i][j]=INF;
				
			}
			
		}
		memset(len,-1,sizeof(len));
	   for(i=1;i<=l;i++)
	   {
		   for(k=1;k<=l;k++) dis[k]=INF;
		   spfa(i);
		   for(k=1;k<=l;k++)
		   {
			   if(k==i) len[i][k]=0;
			   else
			   len[i][k]=dis[k];
		   }
	   }
	  

		memset(conny,-1,sizeof(conny));
		memset(mat,0,sizeof(mat));
		
		for(i=1;i<=num;i++)
		
			scanf("%d%d%d",&s[i].bl,&s[i].st,&s[i].re);
	
		for(i=1;i<=num;i++)
		{
			
			for(j=1;j<=num;j++)
			{
				if(i==j) continue;
				if(len[i][j]==INF) continue;
				if(s[i].st+s[i].re+len[s[i].bl][s[j].bl]<=s[j].st)
					mat[i][j]=1;
			}
		}
		
		
		tot=0;
		for(i=1;i<=num;i++)
		{
			memset(visy,0,sizeof(visy));
			if(find(i)) tot++;
		}
		cout<<num-tot<<endl;
	}
	return 0;
}

• Re:runtime error 啊，spfa+二分图最小路径覆盖 (16) ivanzjj 2011-08-04 16:36:19