Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import Control.Monad
- import Control.Applicative
- import Data.List
- import Debug.Trace
- import Numeric.LinearProgramming
- --Uses the GNU GLPK linear programming library
- spy x = trace (show x) x
- main = do
- n <- readLn
- forM_ [1..n] (\n -> putStr ("Case #" ++ show n ++ ": ") >> solve)
- solve = do
- [n',v',x'] <- spy . words <$> getLine
- let n :: Int ; n = read n'
- let v :: Double ; v = read v'
- let x :: Double ; x = read x'
- [rs,cs] <- transpose <$> forM [1..n] (\_ -> map read . words <$> getLine) :: IO [[Double]]
- if (all (<x) cs || all (>x) cs) then putStrLn "IMPOSSIBLE" else print $ f n v x rs cs
- f n v x rs cs' =
- let hs = zipWith (*) rs cs
- cs = map (subtract x) cs'
- problem = Maximize rs
- bounds = [x :<=: 1 | x <- [1..n]]
- constraint = Dense [hs :==: 0]
- Optimal (maxFlow,_) = spy $ simplex problem constraint bounds
- in v / maxFlow
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement