Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

终于A了

Posted by huangzhilv at 2011-05-31 16:41:58 on Problem 1273
速度很慢

program poj1273;
const
  maxn=300;

type
  tt=array[1..maxn] of longint;

var
  a,b:array[1..maxn,0..maxn] of int64;
  n,m,i:longint;
  x,y,d,f:int64;

function find(var pre:tt):longint;
var
  d,bj:array[1..maxn] of longint;
  l,r,now:longint;
begin
  fillchar(d,sizeof(d),0);
  fillchar(bj,sizeof(bj),0);
  l:=0; r:=1; d[1]:=1; bj[1]:=1; pre[1]:=0;

  while l<r do
  begin
    inc(l);
    now:=d[l];
    for i:=1 to n do
    if (a[now,i]>0) and (bj[i]=0) then
    begin
      inc(r);
      d[r]:=i;
      bj[i]:=1;
      pre[i]:=now;
      if i=n then exit(1);
    end;
  end;
  exit(0);
end;

function ford:integer;
var
  pre:tt;
  i:longint;
  max:int64;
begin
  fillchar(pre,sizeof(pre),0);
  if find(pre)=0 then exit(0);
  i:=n; max:=maxlongint;
  while pre[i]<>0 do
  begin
    if a[pre[i],i]<max then max:=a[pre[i],i];
    i:=pre[i];
  end;
  i:=n;
  while pre[i]<>0 do
  begin
    a[pre[i],i]:=a[pre[i],i]-max;
    a[i,pre[i]]:=a[i,pre[i]]+max;
    i:=pre[i];
  end;
  f:=f+max;
end;

begin
  while not(eof) do
  begin

  fillchar(a,sizeof(a),0);
  fillchar(b,sizeof(b),0);

  readln(m,n);
  for i:=1 to m do
  begin
    readln(x,y,d);
    if x<>y then
    begin
      inc(b[x,0]);
      b[x,b[x,0]]:=y;
      a[x,y]:=a[x,y]+d;
    end;
  end;

  f:=0;
  while ford<>0 do;
  writeln(f);
  end;
end.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator