学步园

题意：

修理公司的工人可以给城市中不同的工厂修理工具。给出各个工厂路径的邻接矩阵，和总任务数，还有每个工厂的工具修理需要的开始时间结束时间。问最少派出多少个工人可以完成所有任务？

分析：跟pku2060几乎是一样的题目，只不过得用一次floyd算法任意俩点之间的最短路径

#include<iostream>

using namespace std;

int inf = 100000000;

struct Task
{
int q;
int s;
int t;
}; 

Task tt[205];

char mat[205][205];
char vstd[205];
int match[205];
int nv;
int dis[25][25]; //i到j的时间

int path(int s)
{
int e;

for(e = 1; e <= nv; e++)
    {
if(mat[s][e] && !vstd[e])
          {
                       vstd[e] = 1;
if(match[e]==-1 || path(match[e]))
                       {
                                match[e] = s;
return 1;
                       }
          }
    }
return 0;
}

int MaxMatch()
{
int s, res = 0;

    memset(match, -1, sizeof(match));

for(s = 1; s <= nv; s++)
    {
          memset(vstd, 0, sizeof(vstd));
          res += path(s);
    }

return res;
}

bool Can(Task a, Task b)
{
if(a.s+a.t+dis[a.q][b.q] <= b.s)
return true;
return false;
}

int main()
{
int q;
int i, j, k;
while(scanf("%d %d", &q, &nv)==2 && (q||nv))
    {
           memset(dis, 0, sizeof(dis));
           memset(mat, 0, sizeof(mat));
           memset(tt, 0, sizeof(tt));

for(i = 1; i <= q; i++)
           {
for(j = 1; j <= q; j++)
                 {
                       scanf("%d", &dis[i][j]);
if(dis[i][j] == -1) dis[i][j] = inf;
                 }
           }

for(k = 1; k <= q; k++)
           {
for(i = 1; i <= q; i++)
                 {
for(j = 1; j <= q; j++)
                       {
if(dis[i][j] > dis[i][k] + dis[k][j])
                                                 dis[i][j] = dis[i][k] + dis[k][j];
                       }
                 }
           }          
for(i = 1; i <= nv; i++)
                 scanf("%d %d %d", &tt[i].q, &tt[i].s, &tt[i].t);           
for(i = 1; i <= nv; i++)
           {
for(j = 1; j <= nv; j++)
                 {
if(i==j) continue;
if(Can(tt[i], tt[j]))
                       {
                                mat[i][j] = 1;
                       }
                 }
           }

int res = nv - MaxMatch();

           printf("%d\n", res);
    }
return 0;
}