注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3996][TJOI2015]线性代数  

2015-04-23 21:43:42|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3996: [TJOI2015]线性代数

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 348  Solved: 267
[Submit][Status][Discuss]

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

Sample Output

2

HINT

 1<=N<=500

Solution

由于A只能取01,因此模型转换为有n个物品,取和不取,同时取有额外收益。最大权闭合图

Code

/**************************************************************
    Problem: 3996
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1424 ms
    Memory:45280 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define N 300000
int n,s,t,l,r,et=1,la[N],q[1<<20],d[N],flow,cur[N],i,j,x;
struct E{int to,flow,nxt;}e[3<<20];
void add(int x,int y,int f){
    e[++et]=(E){y,f,la[x]},la[x]=et;
    e[++et]=(E){x,0,la[y]},la[y]=et;
}
int bfs(){
    memset(d,0,sizeof(d));
    for(q[l=r=0]=t,d[t]=1;l<=r;l++)
    for(i=la[q[l]];i;i=e[i].nxt)
    if(e[i^1].flow&&!d[e[i].to])
    d[q[++r]=e[i].to]=d[q[l]]+1;
    return d[s];
}
#define min(a,b) (a<b?a:b)
int dfs(int x,int ret){
    if(x==t||ret==0)return ret;
    int tmp,flow=0;
    for(int&i=cur[x];i;i=e[i].nxt)
    if(d[e[i].to]+1==d[x]){
        tmp=dfs(e[i].to,min(e[i].flow,ret-flow));
        e[i].flow-=tmp,e[i^1].flow+=tmp;flow+=tmp;
        if(flow==ret)return flow;
    }
    return flow;
}
int maxflow(){
    while(bfs())memcpy(cur,la,sizeof(la)),flow-=dfs(s,1<<30);
    return flow;
}
int main(){
    scanf("%d",&n);s=n*n+n+1,t=s+1;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++){
        scanf("%d",&x);flow+=x;
        if(i==j)add(s,i,x);
        else add(s,i*n+j,x),
        add(i*n+j,i,1<<20),
        add(i*n+j,j,1<<20);
    }
    for(i=1;i<=n;i++){
        scanf("%d",&x);
        add(i,t,x);
    }
    printf("%d\n",maxflow());
}

  评论这张
 
阅读(102)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018