Why Wa#3? Plz help me~~~

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~~~

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~~~

And this is my code(C++)

[code deleted].

*Edited by author 08.11.2010 15:16*

Re: Why Wa#3? Plz help me~~~

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~~~

I use this way to find the answer:

if answer is "Yes" then

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~~~

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*