洛谷-3973 [TJOI2015]线性代数

题目描述
为了提高智商,ZJY开始学习线性代数。她的小伙伴菠萝给她出了这样一个问题:给定一个n×n的矩阵B和一个1×n的矩阵C。求出一个1×n的01矩阵A。使得 D = ( A × B − C ) × A T D=(A×B-C)×A^{\sf T} D=(A×B−C)×AT
最大,其中 A T A^{\sf T} AT
为A的转置。输出D。
输入格式
第一行输入一个整数n。接下来n行输入B矩阵,第i行第j个数代表B接下来一行输入n个整数,代表矩阵C。矩阵B和矩阵C中每个数字都是不过1000的非负整数
输出格式
输出一个整数,表示最大的D。

输入输出样例
输入 #1
3
1 2 1
3 1 0
1 2 3
2 3 7

输出 #1
2
说明/提示

数据范围
对于 30% 的数据，1 ≤ n ≤ 15
对于 100% 的数据，1 ≤ n ≤ 500

解释：可以化简为
D = ( A ∗ B − C ) ∗ A T D=(A*B-C)*A^T D=(A∗B−C)∗AT
= ∑ i = 1 n ( ∑ j = 1 n A j ∗ B j , i − C i ) ∗ A i =\sum_{i=1}^{n}(\sum_{j=1}^{n}A_j*B_{j,i}-C_i)*A_i =∑i=1n​(∑j=1n​Aj​∗Bj,i​−Ci​)∗Ai​
= ∑ i = 1 n ∑ j = 1 n A i ∗ A j ∗ B i , j − ∑ i = 1 n C i ∗ A i =\sum_{i=1}^{n}\sum_{j=1}^{n}A_i*A_j*B_{i,j}-\sum_{i=1}^{n}C_i*A_i =∑i=1n​∑j=1n​Ai​∗Aj​∗Bi,j​−∑i=1n​Ci​∗Ai​
因为题目已经说明了A是一个01串,所以我们可以发现当 A i A_i Ai​
显然为最大权闭合子图模型，套路建图求最小割即可

#include
using namespace std;
const int M=1e6+6,inf=0x3f3f3f3f;
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*10+ch-'0',ch=getchar();return s;
}
int n;
int b[505][505],c[505],id[505][505];
struct edge{int to,w,rev;
};
int d[M],cur[M];vector G[M];
int s,t,tot=0;
queue q;
inline int bfs(){memset(d,-1,sizeof(d));d[s]=0,q.push(s);while(!q.empty()){int u=q.front();q.pop();for(int i=0;i0&&d[e.to]<0){d[e.to]=d[u]+1;q.push(e.to);}}}return d[t]!=-1;
}
int dfs(int u,int f){if(u==t) return f;int w,tot=0;for(int &i=cur[u];i0&&d[e.to]==d[u]+1&&(w=dfs(e.to,min(e.w,f)))){e.w-=w;G[e.to][e.rev].w+=w;f-=w,tot+=w;if(f<=0) break;} }return tot;
}
inline void add_edge(int u,int v,int c){G[u].push_back({v,c,G[v].size()});G[v].push_back({u,0,G[u].size()-1});
}
inline int dinic(){int flow=0;while(bfs()){memset(cur,0,sizeof(cur));flow+=dfs(s,inf);}return flow;
}
int ans=0;
int main(){n=read();for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)b[i][j]=read(),id[i][j]=++tot,ans+=b[i][j];for(int i=1;i<=n;i++) c[i]=read();s=0,t=M-6;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++){add_edge(id[i][j],tot+i,inf);if(i!=j){add_edge(s,id[i][j],b[i][j]+b[j][i]);add_edge(id[i][j],tot+j,inf);}else{add_edge(s,id[i][j],b[i][j]);}}for(int i=1;i<=n;i++) add_edge(tot+i,t,c[i]);printf("%d",ans-dinic());return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！