poj3216
2024-09-13 01:57:15
这是一道描述非常不清楚的题目
首先解释一下,题目中的ti是任务开始时间不是结束时间,
然后维修人员可以理解为可以再任意时间从公司出发;
好,首先不难想到用floyd预处理一下;
然后我们把每个任务看成一个点,显然有些维修员完成一个任务后还可以接着完成别的任务;
这样我们就可以构造出一张有向无环图;
考虑到每个任务这需要我们做一次且仅一次,并且现在我们要求最少的人去覆盖所有的点;
不难想到最小路径覆盖,构造二分图求解即可
const inf=;
type node=record
next,point:longint;
end; var edge:array[..] of node;
p,cx,cy,d,s,w:array[..] of longint;
v:array[..] of boolean;
a:array[..,..] of longint;
len,ans,i,j,n,m,k:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].next:=p[x];
p[x]:=len;
end; function find(x:longint):longint;
var i,y:longint;
begin
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if not v[y] then
begin
v[y]:=true;
if (cy[y]=-) or (find(cy[y])=) then
begin
cx[x]:=y;
cy[y]:=x;
exit();
end;
end;
i:=edge[i].next;
end;
exit();
end; begin
readln(n,m);
while (n<>) do
begin
len:=;
fillchar(p,sizeof(p),);
for i:= to n do
for j:= to n do
begin
read(a[i,j]);
if a[i,j]=- then a[i,j]:=inf;
end;
for k:= to n do
for i:= to n do
if (i<>k) then
for j:= to n do
if (i<>j) and (j<>k) then
a[i,j]:=min(a[i,j],a[i,k]+a[k,j]);
for i:= to m do
readln(w[i],s[i],d[i]);
for i:= to m do
for j:= to m do
begin
if i=j then continue;
if a[w[i],w[j]]+s[i]+d[i]<=s[j] then add(i,j);
end;
ans:=;
fillchar(cx,sizeof(cx),);
fillchar(cy,sizeof(cy),);
for i:= to m do
if cx[i]=- then
begin
fillchar(v,sizeof(v),false);
ans:=ans+find(i);
end;
writeln(m-ans);
readln(n,m);
end;
end.
最新文章
- wpf版扫雷游戏
- oracle is not in the sudoers file. This incident will be reported.
- NSUserDefaults的使用
- 为什么是梯度下降?SGD
- 创建一个三角形类,成员变量三边,方法求周长,创建类主类A来测试它
- C#中堆和栈的区别分析
- sublime好看的主题webstrom破解
- solr 相似查询-MoreLikeThis
- cluster模块实现多进程-让我的代理服务速度飞起来了
- javascript动态创建对象
- 使用bat打开多个cmd窗口执行gulp、node
- logisim元件清单
- linux下的别名机制
- ILRuntime_NewbieGuide—入门
- T-SQL基础(三)之子查询与表表达式
- helm-chart3,函数和管道
- 黄聪:ionic使用ion-nav-bar设置了bar-positive类但在安卓Android设备中无法置底
- Example of Formalising a Grammar for use with Lex &; Yacc
- 转 PHP5+APACHE2.2配置
- Node.js中setTimeout和setInterval的使用