一家维修公司,服务的 Q 街区。每个街区有一定距离,
一天公司收到M修理任务,第i个任务发生在第i个街区,
并且每个任务都有起始时间
ti,完成一个任务需要di时间.修理工必须完成一个任务后,再去另一个.
问要完成这M个任务最少需要多少个修理工?
思路:有向图的最小路径覆盖。先用floyd求出两点间的最短距离,然后建图 若第j个街区任务的开始时间大于等于第i个街区的任务完成时间
+ 路上花费时间 则i到j间连一条边 建立二分图 求最大匹配 。ans = 顶点数 - 最大匹配数。
//328K
79MS
#include
#include
#define Q 25
#define M 205
const int inf = 0x3f3f3f3f;
int mat[Q][Q],edge[M][M];//mat[][]为Q个街区间的距离 edge[i][j] =
1;为i到j有边
int n,m;
int link[M],vis[M];
struct point
{
int
pt,sta,end;//pt 顶点编号,sta开始时间,end完成的时间
}node[M];
bool DFS(int u)
{
for (int v =
1;v <= m;v ++)
if (edge[u][v]&&!vis[v])
{
vis[v] = 1;
if (link[v] == -1 || DFS(link[v]))
{
link[v] = u;
return true;
}
}
return
false;
}
int MaxMatch ()
{
int res =
0;
memset
(link,-1,sizeof(link));
for (int u =
1;u <= m;u ++)
{
memset (vis,0,sizeof(vis));
if (DFS(u))
res ++;
}
return
res;
}
int main ()
{
int
i,j,k,t,d;
while (scanf
("%d%d",&n,&m))
{
if (n == 0 && m == 0)
break;
memset (edge,0,sizeof(edge));
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++)
{
scanf ("%d",&mat[i][j]);
if (mat[i][j] == -1)