这道题教会我们一个道理靠谁也不如靠自己。
当时学长已经讲了，然而一脸懵逼，好吧，上网搜题解，二脸懵逼，于是自己动手，丰衣足食。自己推！
首先就是建模了，这道题谁与谁之间建模已经十分明了，超级源点，超级汇点没跑，重点在权值，首先，依照题意，是“舍弃”，因此基本确认为最小割，那么最小割从哪里割，就是我们每个人都雇佣所赚的钱（由样例可知，实际上是2倍所赚的钱，以下省略“*2”，简称合作金），但先不必算雇佣金，在一开始先只考虑赚钱，那么先说最简单的，两个人都雇佣，那么我们所赚的钱为两人合作金-雇佣两人所花的钱，那么我们割掉的边的流量就应当是雇佣金了，于是乎，连向终点的流量get，即为雇佣金。
于是我们happy的继续推，如果这两个人我都不雇佣，那么我损失的就是雇佣他俩所赚的钱了，而我割的边的流量就是合作金，因为两人均摊，因此不必*2。
最后，也就是个人认为比较复杂的就是一个雇佣一个不雇佣的情况，那么比起两人一起合作所产生的合作金我少的就是两倍合作金+敌对公司让我减少的一倍合作金+我所雇佣的那个人的雇佣金，由之前我们可知我割掉雇佣的那个人与汇点的时候已减少雇佣金，我割掉不雇佣的人与源点的时候以减去一倍合作金，于是乎，剩下的就是两倍合作金了，这就是两人之间的流量，记得开双向哈。
总的来说就是这样，由简到难，由已知边的流量去推未知边的流量，找准总值为关键，实在不行就列个方程，怎样也能搞出来。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
int n,s,zz=,t;
long long co[],a[];
struct ro{
int to,from;
int next;
long long l;
}road[];
void build(int x,int y,long long z){
zz++;
road[zz].l=z;
road[zz].to=y;
road[zz].from=x;
road[zz].next=a[x];
a[x]=zz;
zz++;
road[zz].to=x;
road[zz].from=y;
road[zz].next=a[y];
road[zz].l=;
a[y]=zz;
}
long long sum[];
long long deep[],cur[],cur2[];
bool bfs(){
memset(deep,,sizeof(deep));
queue<int> q1;
q1.push(s);
deep[s]=;
while(!q1.empty())
{
int x=q1.front();
q1.pop();
for(int i=a[x];i>;i=road[i].next)
{
int y=road[i].to;
if(road[i].l>&&(!deep[y]))
{
deep[y]=deep[x]+;
q1.push(y);
}
}
}
if(!deep[t])return ;
return ;
}
long long dfs(int x,long long sum){
if(x==t||!sum) return sum;
for(int i=cur[x];i>;i=road[i].next)
{
cur[x]=i;
int y=road[i].to;
if(road[i].l>&&deep[y]==deep[x]+)
{
int k=dfs(y,min(sum,road[i].l));
if(k)
{
road[i].l-=k;
road[i^].l+=k;
return k;
}
}
}
return ;
}
long long work(){
long long ans=;
memcpy(cur2,a,sizeof(a));
while(bfs())
{
int x;
memcpy(cur,cur2,sizeof(cur2));
while(x=dfs(s,0x7fffffff))
{
ans+=x;
}
}
return ans;
}
long long summ;
int main(){
scanf("%d",&n);
t=n+;
for(int i=;i<=n;i++)
{
scanf("%lld",&co[i]);
}
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
long long x;
scanf("%lld",&x);
if(x)build(i,j,x*);
sum[i]+=x;
}
}
for(int i=;i<=n;i++)
{
build(s,i,sum[i]);
build(i,t,co[i]);
summ+=sum[i];
}
printf("%lld\n",summ-work());
//while(1);
return ;
}