SRM 619 div2 950

给n个点的完全图, 求诱导子图(可空可全图), 最大化利益P, 2<=n<=50
其中每个点有权值Vi, 每条边有权值Eij
若点在子图中则利益P-Vi
若边在子图中则利益P+Eij, 否则不在, 利益P-Eij(若该边有1个节点在子图中则对利益无影响)

举例
..:
点权值{2, 2}
边权值{{0, 1}, {1, 0}}
那么最大P就是空子图, P=-1

观察
..:
初始利益是-S(E)
对任一节点i, 若选入则增加-Vi+S(Eij)利益, S(Eij)是与i相连所有边权和
这样想是不会出现重复计算的, 即每个点是否选入不相干
因为对任意边, 选一个节点增加E, 再选一个又增加E

写出代码
..:

#include <bits/stdc++.h>
using namespace std;

int n, s, r;
class EmployManager {
public:
    int maximumEarnings(vector<int> v, vector<string> e) {
        n=v.size();
        for (int i=0; i<n; i++)
            for (int j=i+1; j<n; j++)
                r-=e[i][j]-'0';
        for (int i=0; i<n; i++) {
            s=0;
            for (int j=0; j<n; j++) s+=e[i][j]-'0';
            if (s-v[i]>0)
                r+=s-v[i];
        }
        return r;
    }
};