首页 > 代码库 > 【bzoj3996】[TJOI2015]线性代数 最大权闭合图
【bzoj3996】[TJOI2015]线性代数 最大权闭合图
题目描述
给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得
D=（A*B-C）*A^T最大。其中A^T为A的转置。输出D
输入
第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.
接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。
输出
输出最大的D
样例输入
3
1 2 1
3 1 0
1 2 3
2 3 7
样例输出
2
题解
网络流最大权闭合图
（推导过程什么的不重要，只要注意一下矩阵乘法不满足结合律。其实看懂结论就行）
由于A是01矩阵，所以bij对答案有贡献的前提是ai和aj都为1；而若ai为1，则会对答案产生贡献-ci
即取bij的前提是取-ci和-cj。
很容易看出这是一个最大权闭合图模型。
连边s->pos(bij)，容量为bij；pos(ci)->t，容量为ci；pos(bij)->pos(ci)、pos(cj)，容量为inf。
然后跑最小割，答案为∑bij-mincut。
MDZZ写个LaTeX真是累死了
#include <cstdio>#include <cstring>#include <queue>#define N 300000#define M 2000000#define inf 0x3f3f3f3fusing namespace std;queue<int> q;int head[N] , to[M] , val[M] , next[M] , cnt = 1 , s , t , dis[N];void add(int x , int y , int z){ to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;}bool bfs(){ int x , i; memset(dis , 0 , sizeof(dis)); while(!q.empty()) q.pop(); dis[s] = 1 , q.push(s); while(!q.empty()) { x = q.front() , q.pop(); for(i = head[x] ; i ; i = next[i]) { if(val[i] && !dis[to[i]]) { dis[to[i]] = dis[x] + 1; if(to[i] == t) return 1; q.push(to[i]); } } } return 0;}int dinic(int x , int low){ if(x == t) return low; int temp = low , i , k; for(i = head[x] ; i ; i = next[i]) { if(val[i] && dis[to[i]] == dis[x] + 1) { k = dinic(to[i] , min(temp , val[i])); if(!k) dis[to[i]] = 0; val[i] -= k , val[i ^ 1] += k; if(!(temp -= k)) break; } } return low - temp;}int main(){ int n , i , j , x , ans = 0; scanf("%d" , &n); s = 0 , t = n * n + n + 1; for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%d" , &x) , add(s , (i - 1) * n + j , x) , add((i - 1) * n + j , i + n * n , inf) , add((i - 1) * n + j , j + n * n , inf) , ans += x; for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , add(i + n * n , t , x); while(bfs()) ans -= dinic(s , inf); printf("%d\n" , ans); return 0;}
【bzoj3996】[TJOI2015]线性代数 最大权闭合图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。