「BZOJ3996」[TJOI2015] 线性代数
Description
给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得
D=（A*B-C）*A^T最大。其中A^T为A的转置。输出D
Input
第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.
接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。
Output
输出最大的D
Sample Input
3
1 2 1
3 1 0
1 2 3
2 3 7
1 2 1
3 1 0
1 2 3
2 3 7
Sample Output
2
HINT
1<=N<=500
题解
倒腾下式子发现是
\(\sum_{i=1}^n \sum_{j=1}^n B_{ij} \times A_i \times A_j – \sum_{i=1}^n A_i \times C_i \)
经典最小割建模
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,T,cnt=1,tot,id; int h[300005],q[300005],last[300005]; struct edge{ int to,next,v; }e[2000005]; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],0};last[v]=cnt; } bool bfs() { int head=0,tail=1; q[0]=0;h[0]=0; for(int i=1;i<=T;i++)h[i]=-1; while(head!=tail) { int x=q[head];head++; for(int i=last[x];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[x]+1; q[tail++]=e[i].to; } } return h[T]!=-1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } int dinic() { int ans=0; while(bfs())ans+=dfs(0,inf); return ans; } int main() { n=read();T=n+n*n+1;id=n; int x; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { x=read();++id; insert(i,id,inf); insert(j,id,inf); insert(id,T,x);tot+=x; } for(int i=1;i<=n;i++) { x=read(); insert(0,i,x); } printf("%d\n",tot-dinic()); return 0; } |
Subscribe
计数器 9787088
OI 课件=>
OI 课件=>