repairing company(dag最小路径覆盖).cpp

杭电acm解题报告2001---2099.

//This problem is basically a minimum path cover problem. 
//Use a direct graph to represent the relations between tasks. 
//If it is possible for a repairman to show up in time for task j after finishing task i, 
//insert an edge emanating from vertex i to vertex j into the graph. 
//Then the minimum number of repairman needed is equal to the path cover number of the graph.
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 30 
#define MMAX 210

int n, m;
int graph[NMAX][NMAX];
struct node {
	int p,t,d;

	bool reachable(const node & nt) {
		if(graph[p][nt.p] == -1) {
			return false;
		}
		if(t+d+graph[p][nt.p] <= nt.t) {
			return true;
		}
		return false;
	}
	bool operator < (const node & nt) const {
		if(t != nt.t) {
			return t < nt.t;
		}
		return d < nt.d;
	}
}task[MMAX];
vector< vector<int> > Bmap;
int mark[MMAX];
bool flag[MMAX];

void Floyd()
{
	int i,j,k;
	for(k=0;k<n;k++) {
		for(i=0;i<n;i++) {
			if(graph[i][k]==-1) {
				continue ;
			}
			for(j=0;j<n;j++) {
				if(graph[k][j]==-1) {
					continue ;
				}
				if((graph[i][j]==-1) || (graph[i][j] > graph[i][k]+graph[k][j])) {
					graph[i][j] = graph[i][k]+graph[k][j];     /*最短路径值*/ 
				}                
			}
		}
	}
}

void make_Bi_graph()
{
	int i,j;
	for(i=0;i<m;i++) {
		for(j=i+1;j<m;j++) {
			if(task[i].reachable(task[j])) {
				Bmap[i].push_back(j);
			}
		}
	}
}

bool dfs(int pos)
{
	int i,l;
	l = Bmap[pos].size();
	for(i=0;i<l;i++) {
		int tp = Bmap[pos][i];
		if(!flag[tp]) {
			flag[tp] = true;
			int pre = mark[tp];
			mark[tp] = pos;
			if(pre == -1 || dfs(pre)) {
				return true;
			}
			mark[tp] = pre;
		}
	}
	return false;
}

int Max_Match()
{
	int i, mmax;
	mmax = 0;
	for(i=0;i<m;i++) {
		memset(flag,0,sizeof(flag));
		if(dfs(i)) {
			mmax ++;
		}
	}
	return mmax;
}

int main()
{
	int i,j;

	while(scanf("%d %d",&n,&m)==2) {
		if(n==0 && m==0) {
			break;
		}
		for(i=0;i<n;i++) {
			for(j=0;j<n;j++) {
				scanf("%d", &graph[i][j]);
			}
		}
		Floyd();
		for(i=0;i<m;i++) {
			scanf("%d %d %d", &task[i].p, &task[i].t, &task[i].d);
			task[i].p --;
		}
		
		sort(task, task+m);
		Bmap.clear();
		Bmap.resize(m+10);
		make_Bi_graph();

		memset(mark,-1,sizeof(mark));
		printf("%d\n", m - Max_Match());
	}
}