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
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
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
#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的难题[有源汇上下界最大流]的更多相关文章
-
BZOJ.3698.XWW的难题(有源汇上下界最大流ISAP)
题目链接 按套路行列作为两部分,连边 \(S->row->column->T\). S向代表行的元素连边cap(A[i][n])(容量上下界为上下取整),代表列的元素向T连边cap( ...
-
BZOJ 3698: XWW的难题 [有源汇上下界最大流]
3698: XWW的难题 题意:(1)A[N][N]=0:(2)矩阵中每行的最后一个元素等于该行前N-1个数的和:(3)矩阵中每列的最后一个元素等于该列前N-1个数的和.给A中的数进行取整操作(可以是 ...
-
【有源汇上下界费用流】BZOJ 3876 [Ahoi2014]支线剧情
题目链接: http://www.lydsy.com:808/JudgeOnline/problem.php?id=3876 题目大意: 给定一张拓扑图(有向无环图),每条边有边权,每次只能从第一个点 ...
-
【有源汇上下界最大流】ZOJ 3229 Shoot the Bullet
题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3229 题目大意: n天给m个女孩拍照(1<=n<= ...
-
POJ2396 Budget [有源汇上下界可行流]
POJ2396 Budget 题意:n*m的非负整数矩阵,给出每行每列的和,以及一些约束关系x,y,>=<,val,表示格子(x,y)的值与val的关系,0代表整行/列都有这个关系,求判断 ...
-
有源汇上下界可行流(POJ2396)
题意:给出一个n*m的矩阵的每行和及每列和,还有一些格子的限制,求一组合法方案. 源点向行,汇点向列,连一条上下界均为和的边. 对于某格的限制,从它所在行向所在列连其上下界的边. 求有源汇上下界可行流 ...
-
BZOJ_2502_清理雪道_有源汇上下界最小流
BZOJ_2502_清理雪道_有源汇上下界最小流 Description 滑雪场坐落在FJ省西北部的若干座山上. 从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道), ...
-
【Loj117】有源汇上下界最小流(网络流)
[Loj117]有源汇上下界最小流(网络流) 题面 Loj 题解 还是模板题. #include<iostream> #include<cstdio> #include< ...
-
ZOJ 3229 Shoot the Bullet(有源汇上下界最大流)
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3442 题目大意: 一个屌丝给m个女神拍照,计划拍照n天,每一天屌丝给 ...
随机推荐
-
Lua: 好的, 坏的, 和坑爹的
好的 小巧: 20000行C代码 可以编译进182K的可执行文件 (Linux下). 可移植: 只要是有ANSI ...
-
php日期时间函数
1,年-月-日echo date('Y-m-j');2007-02-6echo date('y-n-j');07-2-6大写Y表示年四位数字,而小写y表示年的两位数字:小写m表示月份的数字(带前导), ...
-
当浏览器不支持placeholder,所执行的函数
$(function(){ //判断浏览器是否支持placeholder属性 supportPlaceholder='placeholder'in document.createElement('in ...
-
left join 和 left outer join 的区别
left join 和 left outer join 的区别 通俗的讲: A left join B 的连接的记录数与A表的记录数同 A right join ...
-
python3.4 UnicodeDecodeError: &#39;gbk&#39; codec can&#39;t decode byte 0xff in position
python3.4 UnicodeDecodeError: 'gbk' codec can't decode byte 0xff in position 实用python的时候 打开一个csv的文件出 ...
-
error: control may reach end of non-void function [-Werror,-Wreturn-type]
编译出现如下错误 error: control may reach end of non-void function [-Werror,-Wreturn-type] 这个错误可能和编译器有关(在相同代 ...
-
sql 数据库日志收缩
SQL2008 的收缩日志 由于SQL2008对文件和日志管理进行了优化,所以以下语句在SQL2005中可以运行但在SQL2008中已经被取消:(SQL2005)Backup Log DNName w ...
-
POJ1175:Starry Night(bfs)
http://poj.org/problem?id=1175 题目解析: 这个题因为数据的原因可以很水的过,但我因为把1e-8写成了1e-9WA了N遍,一直WA,题目意思很简单就是相似图形(就是求旋转 ...
-
POJ1733 Party game [带权并查集or扩展域并查集]
题目传送 Parity game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10870 Accepted: 4182 ...
-
【转】Visual Studio 选择相同变量高亮
转:http://www.cnblogs.com/stone_w/p/3613760.html 前段时间一直在使用matlab,今天需要使用vs2008,而用惯了matlab,习惯了其中一项选中变量高 ...