Advertisement
Guest User

Untitled

a guest
May 30th, 2015
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.87 KB | None | 0 0
  1. import Control.Monad
  2. import Control.Applicative
  3. import Data.List
  4. import Debug.Trace
  5. import Numeric.LinearProgramming
  6.  
  7. --Uses the GNU GLPK linear programming library
  8.  
  9. spy x = trace (show x) x
  10.  
  11. main = do
  12. n <- readLn
  13. forM_ [1..n] (\n -> putStr ("Case #" ++ show n ++ ": ") >> solve)
  14.  
  15. solve = do
  16. [n',v',x'] <- spy . words <$> getLine
  17. let n :: Int ; n = read n'
  18. let v :: Double ; v = read v'
  19. let x :: Double ; x = read x'
  20. [rs,cs] <- transpose <$> forM [1..n] (\_ -> map read . words <$> getLine) :: IO [[Double]]
  21. if (all (<x) cs || all (>x) cs) then putStrLn "IMPOSSIBLE" else print $ f n v x rs cs
  22.  
  23. f n v x rs cs' =
  24. let hs = zipWith (*) rs cs
  25. cs = map (subtract x) cs'
  26. problem = Maximize rs
  27. bounds = [x :<=: 1 | x <- [1..n]]
  28. constraint = Dense [hs :==: 0]
  29. Optimal (maxFlow,_) = spy $ simplex problem constraint bounds
  30. in v / maxFlow
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement