给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得

输出最大的D

 1<=N<=500

 1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define inf (1<<30)14 #define NN (500010)15 #define N (510)16 #define il inline17 #define RG register18 #define ll long long19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)20 21 using namespace std;22 23 struct edge{ int nt,to,flow,cap; }g[5000010];24 25 int head[NN],dis[NN],q[NN],a[N][N],b[N][N],c[N],d[N],n,S,T,sz,ans,num=1;26 27 il int gi(){28     RG int x=0,q=1; RG char ch=getchar();29     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();30     if (ch==‘-‘) q=-1,ch=getchar();31     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();32     return q*x;33 }34 35 il void insert(RG int from,RG int to,RG int cap){36     g[++num]=(edge){head[from],to,0,cap},head[from]=num; return;37 }38 39 il int bfs(RG int S,RG int T){40     for (RG int i=1;i<=sz;++i) dis[i]=0;41     RG int h=0,t=1; q[t]=S,dis[S]=1;42     while (h<t){43     RG int x=q[++h],v;44     for (RG int i=head[x];i;i=g[i].nt){45         v=g[i].to;46         if (!dis[v] && g[i].cap>g[i].flow){47         q[++t]=v,dis[v]=dis[x]+1;48         if (v==T) return 1;49         }50     }51     }52     return 0;53 }54 55 il int dfs(RG int x,RG int T,RG int a){56     if (x==T || !a) return a; RG int flow=0,f;57     for (RG int i=head[x],v;i;i=g[i].nt){58     v=g[i].to;59     if (dis[v]==dis[x]+1 && g[i].cap>g[i].flow){60         f=dfs(v,T,min(a,g[i].cap-g[i].flow));61         if (!f){ dis[v]=-1; continue; }62         g[i].flow+=f,g[i^1].flow-=f;63         flow+=f,a-=f; if (!a) return flow;64     }65     }66     return flow;67 }68 69 il int maxflow(RG int S,RG int T){70     RG int flow=0;71     while (bfs(S,T)) flow+=dfs(S,T,inf);72     return flow;73 }74 75 il void work(){76     n=gi(),S=++sz,T=++sz;77     for (RG int i=1;i<=n;++i)78     for (RG int j=1;j<=n;++j){79         a[i][j]=++sz,b[i][j]=gi(),ans+=b[i][j];80         insert(a[i][j],T,b[i][j]),insert(T,a[i][j],0);81     }82     for (RG int i=1;i<=n;++i)83     c[i]=gi(),d[i]=++sz,insert(S,d[i],c[i]),insert(d[i],S,0);84     for (RG int i=1;i<=n;++i)85     for (RG int j=1;j<=n;++j)86         if (i!=j){87         insert(d[i],a[i][j],inf),insert(a[i][j],d[i],0);88         insert(d[j],a[i][j],inf),insert(a[i][j],d[j],0);89         } else insert(d[i],a[i][j],inf),insert(a[i][j],d[i],0);90     printf("%d\n",ans-maxflow(S,T)); return;91 }92 93 int main(){94     File("linear");95     work();96     return 0;97 }