这场好搞笑啊，现在想起来还是想笑/xk

简单写一下G题

蛮好的一道状压题。看数据范围八成就是n*2^n的状压了，先盲猜一下状态dp[S]，表示放好的数的下标状态为S的min值，可以看出，我们可以任意顺序把数放到序列里，只要保证他们的贡献不少就可以了。然后看到比较烦人的绝对值，就想办法扔掉它，方法就是我们从小到大放数，这样子能保证每次我放好数x，然后统计贡献的时候，所有已经存在的y都比x小，绝对值就可以扔掉了。具体的，枚举状态S，根据二进制1的个数可以确定这一次操作我方那个数，然后枚举放到哪个位置，比如放到了j，现在考虑他带来的贡献。由于状态的局限性，我们只知道y们有谁，不知道具体的位置。我们拿已经放好的y们和j位置对应的所有二元组取交，交集的大小s就是x作为A-B中的A贡献的次数，然后考虑作为B的贡献，设贡献了t次。假设x在输入的二元组中一共出现了z次，有s+t=z，这样就统计出了作为B贡献的次数。

简单说，就是我保证从小到大放数，这样能去掉绝对值，然后考虑每次把x放到j的贡献，分为两部分，他作为A-B中的A的贡献和B的贡献，因为以后的状态我们都不能记录j位置的数具体是几，只能知道这里放没放数，所以x的贡献必须在这里全部统计完。

#include<bits/stdc++.h>

#define ll long long
#define maxn 1200010
using namespace std;
int n, m, a[21], f[21], z[21], c[maxn];
ll dp[maxn];

int get(int s) {
    int res = 0;
    for (int i = 0; i <= 25; i++)
        if (s & (1 << i))res++;
    return res;
}

void pre(int n) {
    for (int i = 0; i < n; i++)
        c[i] = get(i);
}

int main() {
    freopen("C:\\Users\\yanli\\Desktop\\data.txt", "r", stdin);
    pre(1 << 20);
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; i++)f[i] = z[i] = 0;
        for (int i = 0; i < (1 << n); i++)dp[i] = 1e15;
        for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
        sort(a + 1, a + 1 + n);
        int u, v;
        while (m--) {
            scanf("%d%d", &u, &v);
            z[u]++, z[v]++;
            f[u] |= 1 << v - 1;
            f[v] |= 1 << u - 1;
        }
        dp[0] = 0;
        for (int S = 0; S < (1 << n); S++) {
            int p = get(S);
            for (int j = 1; j <= n; j++)
                if (S & (1 << j - 1)) {
                    int s = c[f[j] & S];//这个还是要预处理，要不多个log
                    int t = z[j] - s;
                    dp[S] = min(dp[S], dp[S ^ (1 << j - 1)] + 1ll * a[p] * (s - t));
                }
        }
        printf("%lld\n", dp[(1 << n) - 1]);
    }
    return 0;
}
/*


20 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 */