#include<iostream>
#include<cstring>
using namespace std;
bool mapp[202][202];
int dis[30][30];
int q,m;
struct node{
	int p,t,d;
}tasks[202];
void ini(){
	memset(mapp,0,sizeof(mapp));
	memset(dis,0,sizeof(dis));
}
int qq[202];
int vm1[202];
int vm2[202];
int pre[202];
int hungary(bool mapp[][202],int v1,int v2){
	int n = 0;
	int current;
	memset(vm1,-1,sizeof(vm1));
	memset(vm2,-1,sizeof(vm2));

	int head,tail;
	int i,j,k;
	for(i =0;i<v1;i++){
		head = tail = 0;
		memset(pre,-2,sizeof(pre));
		for(j = 0;j<v2;j++){
			if(mapp[i][j]){
				qq[tail++] = j;
				pre[j]=  -1;
			}
		}
		while(head<tail){
			current = qq[head];
			if(vm2[current] == -1)break;
			head++;
			for(j = 0;j<v2;j++){
				if(pre[j] == 0xfefefefe && mapp[vm2[current]][j]){
					pre[j] = current;
					qq[tail++] = j;
				}
			}
		}
		if(head == tail)continue;
		while(pre[current] != -1){
			vm1[vm2[pre[current]]] = current;
			vm2[current] = vm2[pre[current]];
			current = pre[current];
		}
		vm1[i] = current;
		vm2[current] = i;
		n++;
	}
	return n;
}


void solve(){
	int i,j,k;
	for(i = 0;i<q;i++){
		for(j = 0;j<q;j++){
			cin>>dis[i][j];
			if(dis[i][j] = -1)dis[i][j] = 100000000;
		}
	}
	//floyd for shortest path
	for(i = 0;i<q;i++){
		for(j = 0;j<q;j++){
			if(dis[j][i] != 100000000){
				for(k= 0 ;k<q;k++){
					if(dis[j][k] > dis[j][i] + dis[i][k] )
						dis[j][k] = dis[j][i] + dis[i][k];
				}
			}
		}
	}
	int p,t,d;
	for(i = 0;i<m;i++){
		cin>>p>>tasks[i].t>>tasks[i].d;
		tasks[i].p = p - 1;
	}
	//build the graph
	for(i = 0;i<m;i++){
		for(j = 0;j<m;j++){
			//if repair man can finish and show up on time 
			if(tasks[i].t + tasks[i].d + dis[tasks[i].p][tasks[j].p] <= tasks[j].t)
				mapp[i][j] = true;
			else 
				mapp[i][j] = false;
		}
	}
	// hungary is a version of b_graph matching
	cout<<m - hungary(mapp,m,m)<<endl;
}

int main(){
	//freopen("in.txt","r",stdin);
	cin>>q>>m;
	while(q!=0 && m != 0){
		ini();
		solve();
		cin>>q>>m;
	}
	return 0;
}

• Re:大牛们帮忙看一下，wa死了 (2287) 123dc4567 2007-04-01 22:01:54
• Re:大牛们帮忙看一下，wa死了 (91) crazyb0y 2007-04-02 14:35:31
  • Re:大牛们帮忙看一下，wa死了 (131) 123dc4567 2007-04-02 20:14:13
  • Re:大牛们帮忙看一下，wa死了 (117) 123dc4567 2007-04-02 20:19:55