【2010国家集训队】人员雇佣
Description
作为一个富有经营头脑的富翁，小L决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,（我们用Ei,j表示i经理对j经理的了解程度），即当经理i和经理j同时被雇佣时，经理i会对经理j做出贡献，使得所赚得的利润增加Ei,j。当然，雇佣每一个经理都需要花费一定的金钱Ai，对于一些经理可能他做出的贡献不值得他的花费，那么作为一个聪明的人，小L当然不会雇佣他。 然而，那些没有被雇佣的人会被竞争对手所雇佣，这个时候那些人会对你雇佣的经理的工作造成影响，使得所赚得的利润减少Ei,j（注意：这里的Ei,j与上面的Ei,j是同一个）。
作为一个效率优先的人，小L想雇佣一些人使得净利润最大。你可以帮助小L解决这个问题吗？Input
第一行有一个整数\(N\leq1000\)表示经理的个数。
第二行有N个整数\(A_i\)表示雇佣每个经理需要花费的金钱。 接下来的N行中一行包含\(N\)个数，表示\(E_{i,j}\)，即经理i对经理j的了解程度。（输入满足\(E_{i,j}=E_{j,i}\)）Output
第一行包含一个整数，即所求出的最大值。
Sample Input
Sample Output
1
Hint
【数据规模和约定】
20%的数据中\(N<=10\) 50%的数据中\(N<=100\) 100%的数据中 \(N<=1000\)，$ E_{i,j}<=int, A_i<=int$二元组关系的网络流。解方程的套路。
我们先假设雇佣了所有的人，却不付出代价，然后再减去最小割的代价。
\(S\)表示雇佣，\(T\)表示不雇佣。
观察下面的图。如果我们割了\(a,b\)，那么我们就少了\(E_{i,j}\)的价值；如果割了\(a,d,f\)，那么我们要付出\(E_{i,j}\)的代价，也就是减少了\(3*E_{i,j}\)的价值；同理割了\(b,e,c\)就减少了\(3*E_{i,j}\)的价值。割了\(e,f\)相当于\(i,j\)都不雇佣，减少\(2*E_{i,j}\)的代价。
代码：
#include#define ll long long#define N 1005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n;struct road { int to,next; int flow;}s[N*N<<2];int h[N],cnt=1;int cur[N];void add(int i,int j,int f,int f2) { s[++cnt]=(road) {j,h[i],f};h[i]=cnt; s[++cnt]=(road) {i,h[j],f2};h[j]=cnt;}int S,T;int dis[N]; queue q;bool bfs() { memset(dis,0x3f,sizeof(dis)); q.push(S); dis[S]=0; while(!q.empty()) { int v=q.front(); q.pop(); for(int i=h[v];i;i=s[i].next) { int to=s[i].to; if(s[i].flow&&dis[to]>dis[v]+1) { dis[to]=dis[v]+1; q.push(to); } } } return dis[T]<1e9;}int dfs(int v,int maxf) { if(v==T) return maxf; int ret=0; for(int &i=cur[v];i;i=s[i].next) { int to=s[i].to; if(s[i].flow&&dis[to]==dis[v]+1) { int dlt=dfs(to,min(maxf,s[i].flow)); s[i].flow-=dlt; s[i^1].flow+=dlt; ret+=dlt; maxf-=dlt; if(!maxf) return ret; } } return ret;}ll dinic() { ll ans=0; while(bfs()) { while(1) { memcpy(cur,h,sizeof(h)); int tem=dfs(S,1e9); if(!tem) break; ans+=tem; } } return ans;}ll e[N][N];ll a[N];ll sum;int main() { n=Get(); for(int i=1;i<=n;i++) a[i]=Get(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) e[i][j]=Get(),sum+=e[i][j]; T=n+1; for(int i=1;i<=n;i++) { ll tem=0; for(int j=1;j<=n;j++) tem+=e[i][j]; add(i,T,tem,0); add(S,i,a[i],0); for(int j=i+1;j<=n;j++) { add(i,j,2*e[i][j],2*e[i][j]); } } ll maxflow=dinic(); cout<