题目描述
有N个节点,节点之间的数据流量以矩阵C的形式给出,其中Cij表示在第i个和第j个节点之间发送的数据流量(Cij = Cji,Cii = 0)。目标是将节点划分为两个不相交的子集A和B,以便最大化和ΣCij(i∈A,j∈B)。
输入描述
第一行输入一个整数,表示节点个数N(2 <= N <= 20)。以下N行,每行包含N个空格分隔的整数,表示流量矩阵C(0 <= Cij <= 10000)。
输出描述
输出一行,包含一个整数,表示A、B之间的最大流量。
样例输入
3
0 50 30
50 0 40
30 40 0
样例输出
90
提示
中,子集A中包含第1和第3个节点,子集B中包含第2个节点,最大流量为50+40=90。