题目描述
给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得
D=（A*B-C）*A^T最大。其中A^T为A的转置。输出D
题解
观察上面那个式子发现，当一个bij有贡献时当且仅当a[i]=1&&a[j]=1。
且当a[i]=1时会产生-c[i]的贡献。
然后我naive的以为这是个二元关系最小割。
其实没那么复杂，我们建立源点向矩阵中的每一个元素连b[i][j]的边，然后每个元素向t连c[i]的边。
然后(i,j)向i和j分别连inf的边。
这样割左边相当于i和j至少有一个不选，割右边相当于全选。
代码
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define N 502 #define M 260020 #define inf 2e9 using namespace std; typedef long long ll; queue<int>q; typedef long long ll; int head[M],deep[M],cur[M],tot=1,n,c[N],b[N][N],top; ll sum,ans; inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } struct edge{int n,to,l;}e[N*N*7]; inline void add(int u,int v,int l){ e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l; e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=0; } inline bool bfs(int s,int t){ memset(deep,0,sizeof(deep)); memcpy(cur,head,sizeof(cur)); q.push(s);deep[s]=1; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].n){ int v=e[i].to; if(!deep[v]&&e[i].l){deep[v]=deep[u]+1;q.push(v);} } } return deep[t]; } ll dfs(int u,int t,int l){ if(u==t||!l)return l; ll flow=0,f; for(int &i=cur[u];i;i=e[i].n){ int v=e[i].to; if(deep[v]==deep[u]+1&&(f=dfs(v,t,min(l,e[i].l)))){ e[i].l-=f;e[i^1].l+=f;flow+=f;l-=f; if(!l)break; } } return flow; } int main(){ n=rd();int s=0,t=n*n+n+1; for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){ b[i][j]=rd(),sum+=b[i][j];++top,add(0,top,b[i][j]); add(top,n*n+i,inf);add(top,n*n+j,inf); } for(int i=1;i<=n;++i)c[i]=rd(),add(n*n+i,t,c[i]); while(bfs(s,t))ans+=dfs(s,t,inf); cout<<sum-ans; return 0; }