3698: XWW的难题[有源汇上下界最大流]

时间:2022-09-22 23:13:26

3698: XWW的难题

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 354  Solved: 178
[Submit][Status][Discuss]

Description

XWW是个影响力很大的人,他有很多的追随者。这些追随者都想要加入XWW教成为XWW的教徒。但是这并不容易,需要通过XWW的考核。
XWW给你出了这么一个难题:XWW给你一个N*N的正实数矩阵A,满足XWW性。
称一个N*N的矩阵满足XWW性当且仅当:(1)A[N][N]=0;(2)矩阵中每行的最后一个元素等于该行前N-1个数的和;(3)矩阵中每列的最后一个元素等于该列前N-1个数的和。
现在你要给A中的数进行取整操作(可以是上取整或者下取整),使得最后的A矩阵仍然满足XWW性。同时XWW还要求A中的元素之和尽量大。

Input

第一行一个整数N,N ≤ 100。
接下来N行每行包含N个绝对值小于等于1000的实数,最多一位小数。

Output

输出一行,即取整后A矩阵的元素之和的最大值。无解输出No。

Sample Input

4
3.1 6.8 7.3 17.2
9.6 2.4 0.7 12.7
3.6 1.2 6.5 11.3
16.3 10.4 14.5 0

Sample Output

129

HINT

【数据规模与约定】

有10组数据,n的大小分别为10,20,30...100。

【样例说明】

样例中取整后满足XWW性的和最大的矩阵为:

3 7 8 18

10 3 0 13

4 1 7 12

17 11 15 0

Source

 

[Submit][Status]

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=;
const int M=1e5+;
struct edge{int v,next,cap;}e[M];int tot=,head[N];
int n,S,T,SS,TT,res,sum,in[N],dis[N],q[M];
double a[N][N];
inline void add(int x,int y,int z){
e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot;
e[++tot].v=x;e[tot].cap=;e[tot].next=head[y];head[y]=tot;
}
bool bfs(int S,int T){
memset(dis,-,sizeof dis);
int h=,t=;q[t]=S;dis[S]=;
while(h!=t){
int x=q[++h];
for(int i=head[x];i;i=e[i].next){
if(e[i].cap&&dis[e[i].v]==-){
dis[e[i].v]=dis[x]+;
if(e[i].v==T) return ;
q[++t]=e[i].v;
}
}
}
return ;
}
int dfs(int x,int T,int f){
if(x==T) return f;
int used=,t;
for(int i=head[x];i;i=e[i].next){
if(e[i].cap&&dis[e[i].v]==dis[x]+){
t=dfs(e[i].v,T,min(e[i].cap,f));
e[i].cap-=t;e[i^].cap+=t;
used+=t;f-=t;
if(!f) return used;
}
}
if(!used) dis[x]=-;
return used;
}
void dinic(int S,int T){
res=;
while(bfs(S,T)) res+=dfs(S,T,2e9);
}
void mapping(){
scanf("%d",&n);
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%lf",&a[i][j]);
}
}
S=n<<|;T=S+;SS=S+;TT=S+;
for(int i=;i<n;i++){
if(a[i][n]!=(int)a[i][n]) add(S,i,);
in[S]-=(int)a[i][n];in[i]+=(int)a[i][n];
}
for(int i=;i<n;i++){
if(a[n][i]!=(int)a[n][i]) add(i+n,T,);
in[i+n]-=(int)a[n][i];in[T]+=(int)a[n][i];
}
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(a[i][j]!=(int)a[i][j]) add(i,j+n,);
in[i]-=(int)a[i][j];in[j+n]+=(int)a[i][j];
}
}
for(int i=;i<=TT;i++){
if(in[i]>) add(SS,i,in[i]),sum+=in[i];
if(in[i]<) add(i,TT,-in[i]);
}
add(T,S,2e9);
}
int main(){
mapping();
dinic(SS,TT);
if(res!=sum){puts("No");return ;}
dinic(S,T);
printf("%d\n",res*);
return ;
}

3698: XWW的难题[有源汇上下界最大流]的更多相关文章

  1. BZOJ&period;3698&period;XWW的难题&lpar;有源汇上下界最大流ISAP&rpar;

    题目链接 按套路行列作为两部分,连边 \(S->row->column->T\). S向代表行的元素连边cap(A[i][n])(容量上下界为上下取整),代表列的元素向T连边cap( ...

  2. BZOJ 3698&colon; XWW的难题 &lbrack;有源汇上下界最大流&rsqb;

    3698: XWW的难题 题意:(1)A[N][N]=0:(2)矩阵中每行的最后一个元素等于该行前N-1个数的和:(3)矩阵中每列的最后一个元素等于该列前N-1个数的和.给A中的数进行取整操作(可以是 ...

  3. 【有源汇上下界费用流】BZOJ 3876 &lbrack;Ahoi2014&rsqb;支线剧情

    题目链接: http://www.lydsy.com:808/JudgeOnline/problem.php?id=3876 题目大意: 给定一张拓扑图(有向无环图),每条边有边权,每次只能从第一个点 ...

  4. 【有源汇上下界最大流】ZOJ 3229 Shoot the Bullet

    题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3229 题目大意: n天给m个女孩拍照(1<=n<= ...

  5. POJ2396 Budget &lbrack;有源汇上下界可行流&rsqb;

    POJ2396 Budget 题意:n*m的非负整数矩阵,给出每行每列的和,以及一些约束关系x,y,>=<,val,表示格子(x,y)的值与val的关系,0代表整行/列都有这个关系,求判断 ...

  6. 有源汇上下界可行流&lpar;POJ2396&rpar;

    题意:给出一个n*m的矩阵的每行和及每列和,还有一些格子的限制,求一组合法方案. 源点向行,汇点向列,连一条上下界均为和的边. 对于某格的限制,从它所在行向所在列连其上下界的边. 求有源汇上下界可行流 ...

  7. BZOJ&lowbar;2502&lowbar;清理雪道&lowbar;有源汇上下界最小流

    BZOJ_2502_清理雪道_有源汇上下界最小流 Description        滑雪场坐落在FJ省西北部的若干座山上. 从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道), ...

  8. 【Loj117】有源汇上下界最小流(网络流)

    [Loj117]有源汇上下界最小流(网络流) 题面 Loj 题解 还是模板题. #include<iostream> #include<cstdio> #include< ...

  9. ZOJ 3229 Shoot the Bullet&lpar;有源汇上下界最大流&rpar;

    题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3442 题目大意: 一个屌丝给m个女神拍照,计划拍照n天,每一天屌丝给 ...

随机推荐

  1. Lua&colon; 好的&comma; 坏的&comma; 和坑爹的

                                   好的       小巧: 20000行C代码 可以编译进182K的可执行文件 (Linux下).       可移植: 只要是有ANSI ...

  2. php日期时间函数

    1,年-月-日echo date('Y-m-j');2007-02-6echo date('y-n-j');07-2-6大写Y表示年四位数字,而小写y表示年的两位数字:小写m表示月份的数字(带前导), ...

  3. 当浏览器不支持placeholder,所执行的函数

    $(function(){ //判断浏览器是否支持placeholder属性 supportPlaceholder='placeholder'in document.createElement('in ...

  4. left join 和 left outer join 的区别

    left join 和 left outer join 的区别 通俗的讲:    A   left   join   B   的连接的记录数与A表的记录数同    A   right   join   ...

  5. python3&period;4 UnicodeDecodeError&colon; &&num;39&semi;gbk&&num;39&semi; codec can&&num;39&semi;t decode byte 0xff in position

    python3.4 UnicodeDecodeError: 'gbk' codec can't decode byte 0xff in position 实用python的时候 打开一个csv的文件出 ...

  6. error&colon; control may reach end of non-void function &lbrack;-Werror&comma;-Wreturn-type&rsqb;

    编译出现如下错误 error: control may reach end of non-void function [-Werror,-Wreturn-type] 这个错误可能和编译器有关(在相同代 ...

  7. sql 数据库日志收缩

    SQL2008 的收缩日志 由于SQL2008对文件和日志管理进行了优化,所以以下语句在SQL2005中可以运行但在SQL2008中已经被取消:(SQL2005)Backup Log DNName w ...

  8. POJ1175&colon;Starry Night&lpar;bfs&rpar;

    http://poj.org/problem?id=1175 题目解析: 这个题因为数据的原因可以很水的过,但我因为把1e-8写成了1e-9WA了N遍,一直WA,题目意思很简单就是相似图形(就是求旋转 ...

  9. POJ1733 Party game &lbrack;带权并查集or扩展域并查集&rsqb;

    题目传送 Parity game Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 10870   Accepted: 4182 ...

  10. 【转】Visual Studio 选择相同变量高亮

    转:http://www.cnblogs.com/stone_w/p/3613760.html 前段时间一直在使用matlab,今天需要使用vs2008,而用惯了matlab,习惯了其中一项选中变量高 ...