C++(clang++11) 解法, 执行用时: 172ms, 内存消耗: 27512K, 提交时间: 2021-02-13 15:26:10

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 300010
#define inf 0x7fffffff
struct node
{
	int y,c,next,ot;
}a[maxn*10];
int len,first[maxn];
int d[maxn],list[maxn*2],head,tail,S,T;
bool vis[maxn];
int mymin(int x,int y)
{
	return (x<y)?x:y;
}
void ins(int x,int y,int c)
{
	len++;
	int now1=len;
	a[len].y=y;
	a[len].c=c;
	a[len].next=first[x];
	first[x]=len;
	len++;
	int now2=len;
	a[len].y=x;
	a[len].c=0;
	a[len].next=first[y];
	first[y]=len;
	a[now1].ot=now2;
	a[now2].ot=now1;
}
bool bfs()
{
	head=1;
	tail=2;
	memset(d,-1,sizeof(d));
	memset(vis,false,sizeof(vis));
	d[S]=1;
	list[head]=S;
	vis[S]=true;
	while(head!=tail)
	{
		int x=list[head];
		for(int k=first[x];k!=-1;k=a[k].next)
		{
			int y=a[k].y;
			if(d[y]==-1&&a[k].c>0)
			{
				d[y]=d[x]+1;
				if(!vis[y])
				{
					list[tail++]=y;
					if(tail>T*2)
					tail=1;
					vis[y]=true;
				}
			 } 
		}
		vis[x]=false;
		head++;
		if(head>T*2)
		head=1;
	}
	return d[T]>0;
}
int dfs(int x,int flow)
{
	if(x==T)
	return flow;
	int minf=0;
	for(int k=first[x];k!=-1;k=a[k].next)
	{
		int y=a[k].y;
		if(d[y]==d[x]+1&&a[k].c>0)
		{
			int p=mymin(flow-minf,a[k].c);
			p=dfs(y,p);
			a[k].c-=p;
			a[a[k].ot].c+=p;
			minf+=p;
			if(minf==flow)
			break;
		}
	}
	if(minf==0)
	d[x]=0;
	return minf;
}
int dinic()
{
	int ret=0;
	while(bfs())
	ret+=dfs(S,inf);
	return ret;
}
int main()
{
	int n,i,j,ls,x,ans=0;
	len=0;
	memset(first,-1,sizeof(first));
	scanf("%d",&n);
	ls=n*n;
	S=n*(n+1)+1;
	T=S+1;
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		scanf("%d",&x);
		ins(S,(i-1)*n+j,x);
		ins((i-1)*n+j,ls+i,inf);
		ins((i-1)*n+j,ls+j,inf);
		ans+=x;
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		ins(ls+i,T,x);
	}
	printf("%d\n",ans-dinic());
	return 0;
}