学步园

Lily runs a repairing company that services the Q blocks in the city. One day the company receives
M repair tasks, the ith of which occurs in block p_i, has a deadline
t_i on any repairman’s arrival, which is also its starting time, and takes a single repairman
d_i time to finish. Repairmen work alone on all tasks and must finish one task before moving on to another. With a map of the city in hand, Lily want to know the minimum number of repairmen that have to be assign to this day’s tasks.

The input contains multiple test cases. Each test case begins with a line containing
Q and M (0 < Q ≤ 20, 0 < M ≤ 200). Then follow
Q lines each with Q integers, which represent a Q ×
Q matrix Δ = {δ_ij}, where δ_ij means a bidirectional road connects the
ith and the jth blocks and requires δ_ij time to go from one end to another. If δ_ij = −1, such a road does not exist. The matrix is symmetric and all its diagonal elements are zeroes. Right below the
matrix are M lines describing the repairing tasks. The ith of these lines contains
p_i, t_i and d_i. Two zeroes on a separate line come after the last test case.

For each test case output one line containing the minimum number of repairmen that have to be assigned.

尼玛我想到最小顶点覆盖去了，其实是最小路径覆盖，我们把任务看成点，那么对于每个人，若他修好i之后可以修好j，那么在i，j之间连一条边，说明i和j可以由一个人完成，之后把最小路径覆盖求出来就行，但是要用floyd求出块和块之间的最短路

#include<map>      
#include<set>      
#include<list>      
#include<stack>      
#include<queue>      
#include<vector>      
#include<cmath>      
#include<cstdio>      
#include<cstring>      
#include<iostream>      
#include<algorithm>      
      
using namespace std;  

bool vis[210];
int mark[210];
int mat[25][25];
int q, m;

struct node
{
	int pi;
	int ti;
	int di;
}repair[210];

struct node2
{
	int next;
	int to;
}edge[210 * 210];
int head[210];
int tot;

void addedge(int from, int to)
{
	edge[tot].to = to;
	edge[tot].next = head[from];
	head[from] = tot++;
}

bool dfs(int u)
{
	for(int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to;
		if(!vis[v])
		{
			vis[v] = 1;
			if(mark[v] == -1 || dfs(mark[v]))
			{
				mark[v] = u;
				return true;
			}
		} 
	}
	return false;
}

int hungary()
{
	int ans = 0;
	memset( mark, -1, sizeof(mark) );
	for(int i = 1; i <= m; i++)
	{
		memset( vis, 0, sizeof(vis) );
		if(dfs(i))
			ans++;
	}
	return ans;
}

int main()
{
	while(~scanf("%d%d", &q, &m))
	{
		if(!q && !m)
			break;
		memset( head, -1, sizeof(head) );
		tot = 0;
		for(int i = 1; i <= q; i++)
			for(int j = 1; j <= q; j++)
			{
				scanf("%d", &mat[i][j]);
				if(mat[i][j] == -1)
					mat[i][j] = 0x3f3f3f3f;
			}
		for(int k = 1; k <= q; k++)
		{
			for(int i = 1; i <= q; i++)
			{
				for(int j = 1; j <= q; j++)
				{
					mat[i][j] =min(mat[i][j], mat[i][k] + mat[k][j]);
				}
			}
		}
		for(int i = 1; i <= m; i++)
		{
			scanf("%d%d%d", &repair[i].pi, &repair[i].ti, &repair[i].di);
		}
		for(int i = 1; i <= m; i++)
		{
			for(int j = 1; j <= m; j++)
			{
				if(i == j)
					continue;
				int u = repair[i].pi;
				int v = repair[j].pi;
				if(mat[u][v] + repair[i].di + repair[i].ti <= repair[j].ti)
				{
					addedge(i, j);
				}
			}
		}
		int ans = hungary();
		printf("%d\n", m - ans);
	}
	return 0;
}