rt

萌新刚学网络流，求大佬捞捞

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
const int N=1e3+5;
const int M=1e4+5;
const int INF=0x3f3f3f3f;
struct Edge{
    int v,w,c,next;
}edge[M];
int n,tot=1,s,t,ans=0,ret=0;
int head[N],cur[N],d[N],vis[N],p[N][N],q[N][N];
inline void add(int u,int v,int w,int c){
    edge[++tot]=(Edge){v,w,c,head[u]},head[u]=tot;
    edge[++tot]=(Edge){u,0,-c,head[v]},head[v]=tot;
}
inline int read(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') {f=-1;} ch=getchar();}
    while(isdigit(ch)) {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
    return s*f;
}
inline void write(int x){
    int top=0,sta[35];
    while(x) {sta[top++]=x%10,x/=10;}
    while(top) {putchar(sta[--top]+'0');}
}
inline int SPFA()
{
	queue <int> q;
	memset(d,0x3f,sizeof(d));
	memcpy(cur,head,sizeof(head));
	q.push(s),d[s]=0;
	while (!q.empty())
	{
		int u=q.front();q.pop();
		vis[u]=0;
		for (int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].v;
			if (d[v]>d[u]+edge[i].c && edge[i].w)
			{
				d[v]=d[u]+edge[i].c;
				if (!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return d[t]==INF?0:1;
}
inline int Dinic(int u,int f)
{
	if (u==t) return f;
	vis[u]=1;int k,res=0;
	for (int i=cur[u];i && f;i=edge[i].next)
	{
		int v=edge[i].v;cur[u]=i;
		if (!vis[v] && edge[i].w && d[v]==d[u]+edge[i].c)
		{
			k=Dinic(v,min(f,edge[i].w));
			if (!k) {d[v]=INF;continue;}
			edge[i].w-=k,edge[i^1].w+=k;
			res+=k,f-=k;ret+=edge[i].c*k;
		}
	}
	vis[u]=0;
	return res;
}
int main()
{
    n=read();s=0,t=n*2+1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) p[i][j]=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) q[i][j]=read();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            add(i,j+n,1,-(p[i][j]*q[i][j]));
    }
    for (int i=1;i<=n;i++) add(s,i,1,0);
    for (int i=1;i<=n;i++) add(i+n,t,1,0);
    while (SPFA()) ans+=Dinic(s,INF);
    printf("%d",-ret);
    return 0;   
}