传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2039
思路：还是二元组建图
先求出总收益，再解方程建图求最小割
题意有些坑
c+d=w[i]+w[j]
a+b=2*E[i][j]
a+d+f=A[j]+3*E[i][j]
b+c+e=A[i]+3*E[i][j]
然后就没有然后了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
const int maxn=1050,maxm=2000010;
const ll inf=1ll<<50;
using namespace std;
int n;
ll sum,E[maxn][maxn],A[maxn],B[maxn],cost[maxn];
struct Flow{
int pre[maxm],now[maxn],son[maxm],tot,dis[maxn],q[maxm+10],head,tail,S,T;ll val[maxm];
void add(int a,int b,ll c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}
void ins(int a,int b,ll c){add(a,b,c),add(b,a,0);}
void ins2(int a,int b,ll c){add(a,b,c),add(b,a,c);}
void init(){memset(now,0,sizeof(now)),tot=1,S=maxn-1,T=maxn-2;}
void build(){
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
A[i]+=E[i][j],A[j]+=E[i][j],ins2(i,j,2ll*E[i][j]);
for (int i=1;i<=n;i++) ins(i,T,cost[i]);
for (int i=1;i<=n;i++) ins(S,i,A[i]);
}
bool bfs(){
memset(dis,-1,sizeof(dis));
q[tail=1]=S,dis[S]=head=0;
while (head!=tail){
if (++head>maxn) head=1;
int x=q[head];
for (int y=now[x];y;y=pre[y])
if (val[y]&&dis[son[y]]==-1){
if (++tail>maxn) tail=1;
dis[son[y]]=dis[x]+1,q[tail]=son[y];
}
}
return dis[T]>0;
}
ll find(int x,ll low){
if (x==T) return low;
int y;ll res=0;
for (y=now[x];y;y=pre[y]){
if (dis[son[y]]!=dis[x]+1||!val[y]) continue;
ll tmp=find(son[y],min(val[y],low));
res+=tmp,low-=tmp,val[y]-=tmp,val[y^1]+=tmp;
if (!low) break;
}
if (!y) dis[x]=-1;
return res;
}
void work(){
ll res=0;
while (bfs()) res+=find(S,inf);
printf("%lld
",sum-res);
}
}F;
int main(){
scanf("%d",&n),F.init();
for (int i=1;i<=n;i++) scanf("%lld",&cost[i]);
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%lld",&E[i][j]),sum+=E[i][j];
F.build(),F.work();
return 0;
}