Discussion @ 1092. Transversal @ Timus Online Judge

Hello. Could anybody tell me how to solve this problem? (See in)

Posted by Safe Bird (USU) 4 Jan 2003 09:12

Someone said that it can be solved by Greedy. Just use net
flow to catch the largest number of "+". And then so. But
they all said that it is a wrong arithmetic. Could you tell
me your way to solve it?

Notice that someone includes sqr(5)

Posted by Safe Bird (USU) 4 Jan 2003 09:16

> Someone said that it can be solved by Greedy. Just use net
> flow to catch the largest number of "+". And then so. But
> they all said that it is a wrong arithmetic. Could you
tell
> me your way to solve it?

I've got ac with this idea. I wanna how to prove it.

Posted by Safe Bird (USU) 4 Jan 2003 11:41

> > Someone said that it can be solved by Greedy. Just use
net
> > flow to catch the largest number of "+". And then so.
But
> > they all said that it is a wrong arithmetic. Could you
> tell
> > me your way to solve it?

Re: I've got ac with this idea. I wanna how to prove it.

Posted by Dwed 8 Apr 2004 21:50

You can't prove it, because there is a counter-eaxample:
2
+----
+----
+----
+----
+----

If Net flow works for most test cases, I think Match of Binary Graph also works

Posted by ahyangyi_newid 23 Apr 2004 06:19

But I got a Output Limit , why?

Posted by Meteor Slayer 23 Apr 2004 12:59

Sorry, I've a simple mistake :(

Posted by Meteor Slayer 23 Apr 2004 13:07

Re: Hello. Could anybody tell me how to solve this problem? (See in)

Posted by Xudong_LI 4 Jun 2016 12:46

Could you tell me what's the meaning of this problem?my english is noot good.The google translation is bad.

Discussion of Problem 1092. Transversal