import fs from 'fs-extra' ; import { createReader , loadFixtures , locateFixtures } from 'jest.setup' ; import path from 'path' ; import { createMcmf } from '../src' ; describe ( 'codeforces' , function ( ) { describe ( 'contest 1082' , function ( ) { test ( 'g' , function ( ) { const mcmf = createMcmf ( ) ; function solve ( content ) { const io = createReader ( content ) ; const [ n , m ] = io . readIntegersOfLine ( ) ; const source = 0 ; const target = n + m + 1 ; mcmf . init ( source , target , n + m + 2 ) ; const nodes = io . readIntegersOfLine ( ) ; for ( let i = 0 ; i < n ; ++ i ) { const weight = nodes [ i ] ; mcmf . addEdge ( i + 1 , target , weight , 1 ) ; } let answer = 0 ; for ( let i = 1 ; i <= m ; ++ i ) { const [ u , v , weight ] = io . readIntegersOfLine ( ) ; const x = n + i ; answer += weight ; mcmf . addEdge ( source , x , weight , 1 ) ; mcmf . addEdge ( x , u , Number . MAX_SAFE_INTEGER , 1 ) ; mcmf . addEdge ( x , v , Number . MAX_SAFE_INTEGER , 1 ) ; } const [ , maxflow ] = mcmf . minCostMaxFlow ( ) ; answer -= maxflow ; return answer ; } const caseDir = locateFixtures ( 'codeforces/1082/g' ) ; const filenames = fs . readdirSync ( caseDir ) . sort ( ) ; for ( const filename of filenames ) { if ( filename . endsWith ( '.in' ) ) { const inputFilepath = path . join ( caseDir , filename ) ; const content = loadFixtures ( inputFilepath ) ; const output = solve ( content ) ; const answerFilepath = inputFilepath . replace ( /\.in$/ , '.out' ) ; const answer = Number ( loadFixtures ( answerFilepath ) ) ; expect ( output ) . toEqual ( answer ) ; } } mcmf . solve ( context => expect ( Object . keys ( context ) ) . toMatchSnapshot ( ) ) ; } ) ; } ) ; describe ( 'contest 277' , function ( ) { test ( 'e' , function ( ) { const mcmf = createMcmf ( ) ; const caseDir = locateFixtures ( 'codeforces/0277/e' ) ; const filenames = fs . readdirSync ( caseDir ) . sort ( ) ; for ( const filename of filenames ) { if ( filename . endsWith ( '.in' ) ) { const inputFilepath = path . join ( caseDir , filename ) ; const content = loadFixtures ( inputFilepath ) ; const output = solve ( content ) ; const answerFilepath = inputFilepath . replace ( /\.in$/ , '.out' ) ; const answer = Number ( loadFixtures ( answerFilepath ) ) ; expect ( Math . abs ( output - answer ) ) . toBeLessThanOrEqual ( 1e-6 ) ; } } mcmf . solve ( context => expect ( Object . keys ( context ) ) . toMatchSnapshot ( ) ) ; function solve ( content ) { const io = createReader ( content ) ; const [ N ] = io . readIntegersOfLine ( ) ; const vertexes = new Array ( N ) ; for ( let i = 0 ; i < N ; ++ i ) { const [ x , y ] = io . readIntegersOfLine ( ) ; vertexes [ i ] = { x , y } ; } vertexes . sort ( ( p , q ) => { if ( p . y === q . y ) return p . x - q . x ; return q . y - p . y ; } ) ; const source = 0 ; const target = N * 2 + 1 ; mcmf . init ( source , target , N * 2 + 2 ) ; for ( let i = 0 ; i < N ; ++ i ) { mcmf . addEdge ( source , i + 1 , 2 , 0 ) ; mcmf . addEdge ( N + i + 1 , target , 1 , 0 ) ; for ( let j = i + 1 ; j < N ; ++ j ) { if ( vertexes [ i ] . y === vertexes [ j ] . y ) continue ; mcmf . addEdge ( i + 1 , N + j + 1 , 1 , dist ( vertexes [ i ] , vertexes [ j ] ) ) ; } } const [ mincost , maxflow ] = mcmf . minCostMaxFlow ( ) ; const answer = maxflow === N - 1 ? mincost : - 1 ; return answer ; } function dist ( p , q ) { const d = ( p . x - q . x ) * ( p . x - q . x ) + ( p . y - q . y ) * ( p . y - q . y ) ; return Math . sqrt ( d ) ; } interface Vertex { x : number ; y : number ; } } ) ; } ) ; } ) ;