import { ICircularQueue } from '@algorithm.ts/queue';

interface IDinicEdge {
    /**
     * The starting node of the arc.
     */
    readonly from: number;
    /**
     * The ending node of the arc.
     */
    readonly to: number;
    /**
     * Capacity of the arc.
     */
    readonly cap: number;
    /**
     * Flow on the arc.
     */
    flow: number;
}
interface IDinic {
    /**
     * Initialize the Dinic algorithm.
     * @param source  the source node
     * @param sink    the sink node
     * @param n       the number of nodes
     */
    init(source: number, sink: number, n: number): void;
    /**
     * Add an edge into the residual network.
     * @param from    the starting node
     * @param to      the ending node
     * @param cap     capacity
     */
    addEdge(from: number, to: number, cap: number): void;
    /**
     * Calculate the maximum flow of the residual network.
     */
    maxflow(): number;
    /**
     * Calculate the minium cut of the residual network.
     */
    mincut(): Array<Readonly<IDinicEdge>>;
}

declare class Dinic implements IDinic {
    protected readonly _cur: number[];
    protected readonly _dist: number[];
    protected readonly _edges: IDinicEdge[];
    protected readonly _G: number[][];
    protected readonly _Q: ICircularQueue<number>;
    protected _N: number;
    protected _source: number;
    protected _sink: number;
    protected _maxflow: number;
    protected _edgesTot: number;
    protected _modifiedTimestamp: number;
    protected _resolvedTimestamp: number;
    constructor();
    init(source: number, sink: number, n: number): void;
    addEdge(from: number, to: number, cap: number): void;
    maxflow(): number;
    mincut(): Array<Readonly<IDinicEdge>>;
    protected _bfs(): boolean;
    protected _dfs(o: number, mif: number): number;
}

export { Dinic };
export type { IDinic, IDinicEdge };