[BZOJ3698] XWW的难题 网络流
2024-09-04 15:30:28
3698: XWW的难题
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 533 Solved: 275
[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
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
n行n列分别看成n个点,s为源点,t为汇点.
s向每一行i连(l[i][n],r[i][n])的边.
每一列i向t连(l[n][i],r[i][n])的边.
每一行i向每一行j连(l[i][j],r[i][j])的边.
求有源有汇有上下界的最大流.
最后答案要乘3.
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int n;
double a[][];
int l[][],r[][];
int s=,t=,S=,T=;
int q[],dis[];
struct edge {
int to,next,f;
}e[];
int head[],cnt;
void add(int u,int v,int w) {
e[cnt].to=v;e[cnt].next=head[u];e[cnt].f=w;head[u]=cnt++;
e[cnt].to=u;e[cnt].next=head[v];e[cnt].f=;head[v]=cnt++;
}
bool bfs() {
memset(dis,-,sizeof(dis));
int h=,tail=;
q[h]=T;
dis[T]=;
while(h!=tail) {
int now=q[h++];if(h==) h=;
for(int i=head[now];i>=;i=e[i].next) {
if(dis[e[i].to]>-||!e[i^].f) continue;
dis[e[i].to]=dis[now]-;
q[tail++]=e[i].to;if(tail==) tail=;
}
}
return dis[S]>=-;
}
int dfs(int now,int a) {
int f=,flow=;
if(now==T) return a;
for(int i=head[now];i>=;i=e[i].next) {
int to=e[i].to;
if(dis[to]==dis[now]+&&e[i].f>) {
f=dfs(to,min(a,e[i].f));
flow+=f;
e[i].f-=f;
e[i^].f+=f;
a-=f;
if(a==) break;
}
}
return flow;
}
int dinic() {
int ans=;
while(bfs()) {ans+=dfs(S,);}
return ans;
}
int main() {
memset(head,-,sizeof(head));
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++) {
scanf("%lf",&a[i][j]);
l[i][j]=(int)a[i][j];
if(a[i][j]==l[i][j]) r[i][j]=l[i][j];
else r[i][j]=l[i][j]+;
}
add(t,s,);
int sum=;
for(int i=;i<n;i++) {add(S,i,l[i][n]);add(s,i,r[i][n]-l[i][n]);add(s,T,l[i][n]);sum+=l[i][n];}
for(int i=;i<n;i++) {add(i+n,T,l[n][i]);add(i+n,t,r[n][i]-l[n][i]);add(S,t,l[n][i]);sum+=l[n][i];}
for(int i=;i<=n-;i++) {
for(int j=;j<=n-;j++) {add(S,j+n,l[i][j]);add(i,T,l[i][j]);add(i,j+n,r[i][j]-l[i][j]);sum+=l[i][j];}
}
if(dinic()==sum) {
S=s,T=t;
printf("%d\n",dinic()*);
}
else printf("No\n");
}
/* */
最新文章
- acm算法模板(4)
- [译]开始学习webpack
- POJ 1160 Post Office
- MP3播放器的实现
- ElasticSearch D3
- Centos安装vncserver服务
- 为什么MOBA、“吃鸡”游戏不推荐用tcp协议——实测数据
- File类中的list和listFiles方法
- 蓝桥杯 基础练习 之 FJ的字符串
- NumPy简介
- mysql免解压版的配置
- xshell 使用root 连接ubuntu server
- 7个小技巧,解决eclipse卡顿问题
- SqlBulkCopy 批量插入
- js 提示框的实现---组件开发之(一)
- 解决:CentOS下的 error while loading shared libraries: libmysqlclient.so.16: cannot open shared object file: No such file or dir
- 跨域(Cross-Domain) AJAX for IE8 and IE9
- HUST 1017 Exact cover(DLX精确覆盖)
- 在win7/8下搭建简易的无线平台
- 校验 CentOS 7 镜像文件
热门文章
- 大数据Hadoop-1
- P4109 [HEOI2015]定价
- Java Web开发之路(一)——环境配置
- 洛谷P3763 [Tjoi2017]DNA 【后缀数组】
- EditPlus直接连接Linux服务器编辑文本文件
- git使用笔记(九)操作原理
- 关于session variables 和 global variables
- Codeforces Round #525 (Div. 2)D. Ehab and another another xor problem
- 用spring的@Validated注解和org.hibernate.validator.constraints.*的一些注解在后台完成数据校验
- lwIP RAW_API