Description
给出一个 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的非负整数。
Output
输出最大的D
3
1 2 1
3 1 0
1 2 3
2 3 7
Sample Output
2
HINT
1<=N<=500
想法
把D=（A*B-C）*A^T化简一下得出
\(D= \sum\) \(B_{i,j}A_iA_j\) - \(\sum\) \(C_iA_i\)
由于A为01矩阵，所以可将原问题考虑成每一个 \(A_i\) 是否选的问题 若要选 \(A_i\) 与 \(A_j\) ，即在最终答案中加上 \(B_{i,j}\) ，必须在答案中减去 \(C_i\) 与 \(C_j\) 可以发现这是一个“最大权闭合图”问题 将 \(B_{i,j}\) 及 \(C_i\) 当做节点，点权即为 \(B_{i,j}\) 及 \(C_i\) 的值。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 200000000
using namespace std;
typedef long long ll;
const int N = 505;
const int M = 505*505+505;
struct node{
int v,f;
node *next,*rev;
}pool[N*N*8+N*2],*h[M];
int cnt;
void addedge(int u,int v,int f){
node *p=&pool[++cnt],*q=&pool[++cnt];
p->v=v;p->next=h[u];h[u]=p; p->f=f;p->rev=q;
q->v=u;q->next=h[v];h[v]=q; q->f=0;q->rev=p;
}
int S,T;
int level[M];
int que[M];
bool bfs(){
int head=0,tail=0,u,v;
for(int i=S;i<=T;i++) level[i]=-1;
level[S]=1;
que[tail++]=S;
while(head<tail){
u=que[head++];
for(node *p=h[u];p;p=p->next)
if(p->f && level[v=p->v]==-1){
level[v]=level[u]+1;
que[tail++]=v;
}
if(level[T]!=-1) return true;
}
return false;
}
int find(int u,int f){
int v,s=0,t;
if(u==T) return f;
for(node *p=h[u];p;p=p->next)
if(s<f && level[v=p->v]==level[u]+1){
t=find(v,min(p->f,f-s));
if(t){
s+=t;
p->f-=t;
p->rev->f+=t;
}
}
if(!s) level[u]=-1;
return s;
}
int dinic(){
int f=0;
while(bfs()) f+=find(S,INF);
return f;
}
int b[N][N],c[N];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
int sum=0;
S=0; T=n*n+n+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
sum+=b[i][j];
addedge(S,(i-1)*n+j,b[i][j]);
addedge((i-1)*n+j,n*n+i,INF);
addedge((i-1)*n+j,n*n+j,INF);
}
for(int i=1;i<=n;i++)
addedge(n*n+i,T,c[i]);
sum-=dinic();
printf("%d\n",sum);
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/8414474.html
