import networkx as nx
from time import time
import numpy as np
from collections import defaultdict
import random


total_penalty = 0

def simple_cycles(G):
    """Find simple cycles (elementary circuits) of a directed graph.
    A `simple cycle`, or `elementary circuit`, is a closed path where
    no node appears twice. Two elementary circuits are distinct if they
    are not cyclic permutations of each other.
    This is a nonrecursive, iterator/generator version of Johnson's
    algorithm [1]_.  There may be better algorithms for some cases [2]_ [3]_.
    Parameters
    ----------
    G : NetworkX DiGraph
       A directed graph
    Returns
    -------
    cycle_generator: generator
       A generator that produces elementary cycles of the graph.
       Each cycle is represented by a list of nodes along the cycle.
    Examples
    --------
    >>> G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)])
    >>> len(list(nx.simple_cycles(G)))
    5
    To filter the cycles so that they don't include certain nodes or edges,
    copy your graph and eliminate those nodes or edges before calling
    >>> copyG = G.copy()
    >>> copyG.remove_nodes_from([1])
    >>> copyG.remove_edges_from([(0, 1)])
    >>> len(list(nx.simple_cycles(copyG)))
    3
    Notes
    -----
    The implementation follows pp. 79-80 in [1]_.
    The time complexity is `O((n+e)(c+1))` for `n` nodes, `e` edges and `c`
    elementary circuits.
    References
    ----------
    .. [1] Finding all the elementary circuits of a directed graph.
       D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
       http://dx.doi.org/10.1137/0204007
    .. [2] Enumerating the cycles of a digraph: a new preprocessing strategy.
       G. Loizou and P. Thanish, Information Sciences, v. 27, 163-182, 1982.
    .. [3] A search strategy for the elementary cycles of a directed graph.
       J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS,
       v. 16, no. 2, 192-204, 1976.
    See Also
    --------
    cycle_basis
    """
    def _unblock(thisnode,blocked,B):
        stack=set([thisnode])
        while stack:
            node=stack.pop()
            if node in blocked:
                blocked.remove(node)
                stack.update(B[node])
                B[node].clear()

    # Johnson's algorithm requires some ordering of the nodes.
    # We assign the arbitrary ordering given by the strongly connected comps
    # There is no need to track the ordering as each node removed as processed.
    subG = type(G)(G.edges()) # save the actual graph so we can mutate it here
                              # We only take the edges because we do not want to
                              # copy edge and node attributes here.
    sccs = list(nx.strongly_connected_components(subG))
    while sccs:
        scc=sccs.pop()
        # order of scc determines ordering of nodes
        startnode = scc.pop()
        # Processing node runs "circuit" routine from recursive version
        path=[startnode]
        blocked = set() # vertex: blocked from search?
        closed = set() # nodes involved in a cycle
        blocked.add(startnode)
        B=defaultdict(set) # graph portions that yield no elementary circuit
        stack=[ (startnode,list(subG[startnode])) ]  # subG gives component nbrs
        while stack:
            thisnode,nbrs = stack[-1]
            if nbrs:
                nextnode = nbrs.pop()
#                    print thisnode,nbrs,":",nextnode,blocked,B,path,stack,startnode
#                    f=raw_input("pause")
                if nextnode == startnode:
                    yield path[:]
                    closed.update(path)
#                        print "Found a cycle",path,closed
                elif nextnode not in blocked and len(stack) < 5:
                    path.append(nextnode)
                    stack.append( (nextnode,list(subG[nextnode])) )
                    closed.discard(nextnode)
                    blocked.add(nextnode)
                    continue
            # done with nextnode... look for more neighbors
            if not nbrs:  # no more nbrs
                if thisnode in closed:
                    _unblock(thisnode,blocked,B)
                else:
                    for nbr in subG[thisnode]:
                        if thisnode not in B[nbr]:
                            B[nbr].add(thisnode)
                stack.pop()
#                assert path[-1]==thisnode
                path.pop()
        # done processing this node
        subG.remove_node(startnode)
        H=subG.subgraph(scc)  # make smaller to avoid work in SCC routine
        sccs.extend(list(nx.strongly_connected_components(H)))


def is_node_disjoint(cycles, cycle):
    """ returns if any node in cycle is in any cycle in cycles"""

    nodes_in_cycles = set()
    nodes_in_cycle = set()
    for c in cycles:
        for edge in c:
            for node in edge:
                nodes_in_cycles.add(node)

    for edge in cycle:
        for node in edge:
            nodes_in_cycle.add(node)

    return len(nodes_in_cycles.intersection(nodes_in_cycle)) == 0

def temp_is_node_disjoint(cycles, cycle):
    nodes_in_cycles = set()
    nodes_in_cycle = set(cycle)
    for cycle in cycles:
        for node in cycle:
            nodes_in_cycles.add(node)
    return len(nodes_in_cycle.intersection(nodes_in_cycles)) == 0

def penalty(treated_cycles, children, num_vertices):

    output = num_vertices + len(children)
    #print "Total possible penalty: " + str(output)
    #print "Treated cycles: " + str(treated_cycles)
    for cycle in treated_cycles:
        for edge in cycle:
            if edge[0] in children:
                output -= 2
            else:
                output -= 1
    return output

def temp_penalty(treated_cycles, children, num_vertices):

    output = num_vertices + len(children)
    #print "Total possible penalty: " + str(output)
    #print "Treated cycles: " + str(treated_cycles)
    for cycle in treated_cycles:
        for node in cycle:
            if node in children:
                output -= 2
            else:
                output -= 1
    return output

def write_simple_cycles_to_file(treated_cycles, f):

    line = ""
    if len(treated_cycles) == 0:
        f.write("None\n")
        return
    for cycle in treated_cycles:
        for node in cycle:
            line = line + str(node) + " "
        # remove trailing space
        line = line[:-1]
        line += "; "
    # remove trailing ;
    f.write(line[:-2] + "\n")

def write_dfs_cycles_to_file(treated_cycles, f):
    line = ""
    if len(treated_cycles) == 0:
        f.write("None\n")
        return
    for cycle in treated_cycles:
        for edge in cycle:
            line = line + str(edge[0]) + " "
        line = line[:-1]
        line += "; "
    # remove trailing ;
    f.write(line[:-2] + "\n")

solutions = open("solutions.out", "w")

files = range(1, 493)
for w in files:
    print 'Processing file %s' % (w)
    f = open('phase1-processed/' + str(w) + '.in', 'r')
    n = int(f.readline()[:-1])



    children_line = f.readline()[:-1].strip()
    if len(children_line) > 0:
        children = np.array(map(int, children_line.split(" ")))
    else:
        children = np.array([])
    adults = np.setdiff1d(np.arange(n), children)
    adj = np.ndarray(shape=(n,n))
    for i in range(n):
        adj[i] = np.array(f.readline().split(' ')[:n])
    f.close()

    G = nx.DiGraph()

    G.add_nodes_from(adults, weight=1)
    G.add_nodes_from(children, weight=2)
    for i in range(adj.shape[0]):
        for j in range(adj.shape[1]):
            if adj[i][j] == 1:
                G.add_edge(i,j)


    treated_cycles = []
    alternate_treated_cycles = []
    untreated_cycles = []
    untreated_vertices = set(range(n))
    treated_vertices = set()



    # use Johnson's to find all cycles
    if n < 50:
        all_cycles = list(simple_cycles(G))
        valid_cycles = [cycle for cycle in all_cycles if len(cycle) <= 5]
        valid_cycles = sorted(valid_cycles, key=lambda x : -len(x))

        # greedily add all cycles that don't share vertices
        longest_cycle_passed = False
        for cycle in valid_cycles:

            if temp_is_node_disjoint(treated_cycles, cycle):
                treated_cycles.append(cycle)
                for node in cycle:
                    if node in untreated_vertices:
                        untreated_vertices.remove(node)
                    treated_vertices.add(node)
            if longest_cycle_passed and temp_is_node_disjoint(alternate_treated_cycles, cycle):
                alternate_treated_cycles.append(cycle)
            else:
                untreated_cycles.append(cycle)

            longest_cycle_passed = True


        instance_penalty = min(temp_penalty(treated_cycles, children, n), \
                               temp_penalty(alternate_treated_cycles, children, n))
        total_penalty += instance_penalty
        #print "Penalty: " + str(instance_penalty)
        write_simple_cycles_to_file(treated_cycles, solutions)

    else:

        valid_cycles = []
        for node in random.sample(children, len(children)):
            try:
                cycle = list(nx.find_cycle(G, source=node))
                G.remove_edges_from(cycle)
                if len(cycle) <= 5:
                    valid_cycles.append(cycle)
            except:
                pass
        for node in random.sample(adults, len(adults)):
            try:
                cycle = list(nx.find_cycle(G, source=node))
                G.remove_edges_from(cycle)
                if len(cycle) <= 5:
                    valid_cycles.append(cycle)
            except:
                pass

        longest_cycle_passed = False
        for cycle in valid_cycles:

            if is_node_disjoint(treated_cycles, cycle):
                treated_cycles.append(cycle)
                for node in cycle:
                    if node in untreated_vertices:
                        untreated_vertices.remove(node)
                    treated_vertices.add(node)
            if longest_cycle_passed and is_node_disjoint(alternate_treated_cycles, cycle):
                alternate_treated_cycles.append(cycle)
            else:
                untreated_cycles.append(cycle)

            longest_cycle_passed = True

        instance_penalty = min(penalty(treated_cycles, children, n),\
                               penalty(alternate_treated_cycles, children, n))
        total_penalty += instance_penalty

        write_dfs_cycles_to_file(treated_cycles, solutions)
        #print "Penalty: " + str(instance_penalty)



print total_penalty
solutions.close()