SPOJ 1846 — Project File Dependencies (code: PFDEP)
题意见下:
Killa.sqybi 20:01:20
就是说
Killa.sqybi 20:01:21
有n个任务
Killa.sqybi 20:01:24
m个限制条件
Killa.sqybi 20:01:37
每个限制条件都这样描述:
t0 k t1 t2 .. tk
Killa.sqybi 20:01:46
表示t0的完成需要他
Killa.sqybi 20:01:52
需要t1..tk的完成
Killa.sqybi 20:02:03
让你输出一个完成序列
Killa.sqybi 20:02:12
保证靠前的数越小越好
Killa.sqybi 20:02:16
没了
就这样…建立个有向图随便写个n^2的topsort就AC了.注意如果当前有多个点入度为0,那么选择编号最小的.
{
SPOJ 1846; Project File Dependencies; PFDEP
- sqybi’s code
- Topsort
}
//for my winsty
program pfdep_sqybi;
const
nn = 100;
var
n, m, i, j, k, x, y, t: longint;
ind: array[1..nn]of longint;
d: array[1..nn, 1..nn]of boolean;
begin
readln(n, m);
for i:=1 to m do begin
read(x);
read(k);
for j:=1 to k do begin
read(y);
inc(ind[x]);
d[y, x] := true;
end;
readln;
end;
for i:=1 to n do begin
for j:=1 to n do
if ind[j] = 0 then begin
t := j;
break;
end;
for j:=1 to n do
if d[t, j] then dec(ind[j]);
ind[t] := -1;
write(t, ‘ ‘);
end;
end.
阅读(79 次)