U108001 情侣

题目背景

FFF 团正在策划一场行动……

题目描述

这场行动准备在一座城市实施。这座城市有 n 个小镇编号为 1,2,⋯,n，小镇两两之间都有一条双向道路连接。

FFF 团拿到了一张图，上面标明了小镇两两之间的道路上的情侣对数。

团长小 A 命令你去把这些情侣都烧掉。当然，他也会给你很多奖赏。

具体来说，是这样的：每次，你可以选择某一个小镇 x，然后把与 x 相连的所有道路上的情侣都烧掉。如果你这一次烧掉了 t 对情侣，那么小 A 会给你 t^2 元的奖励。你可以这么做多次，直到所有情侣都被烧光为止。

你当然想尽快烧了所有情侣，但是你想先算算你的最大收益是多少。

注意，情侣一旦被烧掉就不存在了。比如，你在城市 1 烧了一次，然后在城市 2 烧了一次，那么第二次就不会烧到(1,2) 这条路上的情侣。

输入格式

第一行一个整数 n，表示小镇的个数。

接下来 n 行，第 i 行 n 个整数 ai1,ai2,ai3…ain 表示边 (i,j*) 上的情侣有多少对。

输出格式

一行一个整数，表示你能获得的最大收益。

输入输出样例

输入 #1

1
2
3
4
3
0 1 2
1 0 1
2 1 0

输出 #1

1
10

dp[ s ] 表示当前烧了 s 集合个城市，烧掉最多情侣。转移方程 ：dp[s]=max(dp[s^(1<<(i-1))]+ val*val ,dp[s]); ​ val 为 s^(1<<(i-1))​ (s 中删除 i 城市) 集合下，删掉 i 带来的价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int MAX=30;
int n,g[MAX][MAX];
int dp[1<<22];
int main(){
	freopen("in","r",stdin);
	sf(n);
	fi(i,1,n+1)
		fi(j,1,n+1){
			sf(g[i][j]);
		}
	fi(s,0,1<<n){
		fi(i,1,n+1){
			if(s&(1<<(i-1))){
				if(s==(1<<(i-1))){
					int val=0;
					fi(k,1,n+1){
						if(i!=k && g[i][k]){
							val += g[i][k];
						}
					}
					dp[s]= val*val;
				}else {
					int val=0;
					fi(k,1,n+1){
						if(i!=k && g[i][k] && !(s&(1<<(k-1)))){
							val += g[i][k];
						}
					}
					dp[s]=max(dp[s^(1<<(i-1))]+val*val,dp[s]);
				}
			}
		}
	}
	pf(dp[(1<<n)-1]);
	return 0;
}