ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1774. Barber of the Army of Mages

Why Wa#3? Plz help me~~~
Posted by William Chou 10 Oct 2010 09:05
I use dinic to solve this problem.
but wa#3.
I think maxflow can work it out.
I don't know why.
could any one give me some test data.
Thank you!

Edited by author 10.10.2010 09:05
Re: Why Wa#3? Plz help me~~~
Posted by svr 10 Oct 2010 09:14
You are right!
This is absolutely maxflow problem.
But in my reprizetory I didn't find variant of algo
on 300*2000 vertices graph.
P.S.AC!!!!
Ford_Falkerson!
n=102+2000=2012
m=n+2000*n+200~200000
F<=2*n=200
complex=O((n+m)*F)~40 000 000 -normaly

Edited by author 10.10.2010 14:06
Re: Why Wa#3? Plz help me~~~
Posted by William Chou 10 Oct 2010 17:52
My MAXN=2200;
MAXM=2200000;
but I still wa#3...
I want to ask a question:
Does this problem have Special Judge?

Edited by author 10.10.2010 19:44
Re: Why Wa#3? Plz help me~~~
Posted by William Chou 10 Oct 2010 17:54
And this is my code(C++)
[code deleted].

Edited by author 08.11.2010 15:16
Re: Why Wa#3? Plz help me~~~
Posted by William Chou 10 Oct 2010 18:11
My node 0 to Max is for time,
and S will link to every time node(flow=k).
node Max+1 to Max+N is for people,
time node will link to the people node which includes this time(flow=1).
then people node will link to T(flow=2).
S=MAXN-1,
T=Max+N+1.
Re: Why Wa#3? Plz help me~~~
Posted by William Chou 10 Oct 2010 19:45
I use this way to find the answer:
I will regard the vertice which flow is full as answer.
Is it right?
I think it can give me a feasible answer.
but I can't ensure it's a minimal answer...
so I wonder is there any special judge.

Edited by author 10.10.2010 19:46

Edited by author 11.10.2010 11:41
Re: Why Wa#3? Plz help me~~~
Posted by William Chou 11 Oct 2010 11:40
now,I get AC.

I have made a stupid mistake.

For the input t[i] ans s[i],

I think it means the i-th recruit will wait from t[i] to s[i]...

but it means he will wait from t[i] to t[i]+s[i]-1...

be careful~

Edited by author 08.11.2010 15:20