「BZOJ3698」「FJ2014集训」XWW的难题

2014年7月20日4,7511

「问题描述」

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中的元素之和尽量大。

「输入文件」

第一行一个整数N,N≤ 100。

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

「输出文件」

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

「样例输入输出」

novel.in	novel.out
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	129

「数据规模与约定」

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

「样例说明」

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

3 7 8 18

10 3 0 13

4 1 7 12

17 11 15 0

「题解」

直接上下界网络流就行，跟poj2396很像。。。

md最后一天集训交了这么一题，还对拍了一下，讲评的时候在测评结果上找不到名字，以为爆零了，后来才知道提交没成功T T

害我重写一次

用emacs还是觉得很吃力啊

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 1000000000
using namespace std;
int S,T,SS,TT;
int n,cnt=1,tot,ans;
int h[205],q[205],in[205],last[205],cur[205];
double a[205][205];
struct data{int to,next,v;}e[100005];
void ins(int u,int v,int w)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,0);}
bool bfs(int x,int y)
{
    for(int i=1;i<=TT;i++)h[i]=-1;
    h[x]=0;q[0]=x;
    int head=0,tail=1;
    while(head!=tail)
    {
		int now=q[head];head++;
		for(int i=last[now];i;i=e[i].next)
			if(e[i].v&&h[e[i].to]==-1)	    
            {
				h[e[i].to]=h[now]+1;
				q[tail++]=e[i].to;
			}
    }
    return h[y]!=-1;
}
int dfs(int x,int y,int f)
{
    if(x==y)return f;
    int w,used=0;
    for(int i=cur[x];i;i=e[i].next)
		if(h[e[i].to]==h[x]+1)    
		{
			w=f-used;w=dfs(e[i].to,y,min(e[i].v,w));
			e[i].v-=w;if(e[i].v)cur[x]=i;
			e[i^1].v+=w;used+=w;if(used==f)return f;
		}
    if(!used)h[x]=-1;
    return used;
}
void build()
{
    for(int i=1;i<n;i++)
    {
		if(a[i][n]!=(int)a[i][n])
			insert(S,i,1);
		in[S]-=(int)a[i][n];in[i]+=(int)a[i][n];
    }
    for(int i=1;i<n;i++)
    {
		if(a[n][i]!=(int)a[n][i])
			insert(i+n,T,1);
		in[i+n]-=(int)a[n][i];in[T]+=(int)a[n][i];
    }
    for(int i=1;i<n;i++)
		for(int j=1;j<n;j++)
		{
			if(a[i][j]!=(int)a[i][j])
				insert(i,j+n,1);
			in[i]-=(int)a[i][j];in[j+n]+=(int)a[i][j];
		}
    for(int i=1;i<=TT;i++)
		if(in[i]>0){tot+=in[i];insert(SS,i,in[i]);}
		else insert(i,TT,-in[i]);

}
void dinic(int x,int y)
{
    while(bfs(x,y)){for(int i=1;i<=TT;i++)cur[i]=last[i];ans+=dfs(x,y,inf);}
}
int main()
{
    scanf("%d",&n);
    S=2*n+1;T=S+1;SS=T+1;TT=SS+1;
    for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%lf",&a[i][j]);
    build();
    insert(T,S,inf);
    dinic(SS,TT);
    if(tot!=ans){printf("No");return 0;}
    ans=0;
    dinic(S,T);
    printf("%d",ans*3);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 1000000000

using namespace std;

int S,T,SS,TT;

int n,cnt=1,tot,ans;

int h[205],q[205],in[205],last[205],cur[205];

double a[205][205];

struct data{int to,next,v;}e[100005];

void ins(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

}

void insert(int u,int v,int w)

{ins(u,v,w);ins(v,u,0);}

bool bfs(int x,int y)

{

for(int i=1;i<=TT;i++)h[i]=-1;

h[x]=0;q[0]=x;

int head=0,tail=1;

while(head!=tail)

{

int now=q[head];head++;

for(int i=last[now];i;i=e[i].next)

if(e[i].v&&h[e[i].to]==-1)

{

h[e[i].to]=h[now]+1;

q[tail++]=e[i].to;

}

return h[y]!=-1;

}

int dfs(int x,int y,int f)

{

if(x==y)return f;

int w,used=0;

for(int i=cur[x];i;i=e[i].next)

if(h[e[i].to]==h[x]+1)

{

w=f-used;w=dfs(e[i].to,y,min(e[i].v,w));

e[i].v-=w;if(e[i].v)cur[x]=i;

e[i^1].v+=w;used+=w;if(used==f)return f;

}

if(!used)h[x]=-1;

return used;

}

void build()

{

for(int i=1;i<n;i++)

{

if(a[i][n]!=(int)a[i][n])

insert(S,i,1);

in[S]-=(int)a[i][n];in[i]+=(int)a[i][n];

}

for(int i=1;i<n;i++)

{

if(a[n][i]!=(int)a[n][i])

insert(i+n,T,1);

in[i+n]-=(int)a[n][i];in[T]+=(int)a[n][i];

}

for(int i=1;i<n;i++)

for(int j=1;j<n;j++)

{

if(a[i][j]!=(int)a[i][j])

insert(i,j+n,1);

in[i]-=(int)a[i][j];in[j+n]+=(int)a[i][j];

}

for(int i=1;i<=TT;i++)

if(in[i]>0){tot+=in[i];insert(SS,i,in[i]);}

else insert(i,TT,-in[i]);

}

void dinic(int x,int y)

{

while(bfs(x,y)){for(int i=1;i<=TT;i++)cur[i]=last[i];ans+=dfs(x,y,inf);}

}

int main()

{

scanf("%d",&n);

S=2*n+1;T=S+1;SS=T+1;TT=SS+1;

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

scanf("%lf",&a[i][j]);

build();

insert(T,S,inf);

dinic(SS,TT);

if(tot!=ans){printf("No");return 0;}

ans=0;

dinic(S,T);

printf("%d",ans*3);

return 0;

}

« 「BZOJ2502」清理雪道「BZOJ3876」[Ahoi2014] 支线剧情 »

zld3794955

给写上下界网络流的hzwer神犇跪烂烂…

hzwer.com _ Home | http://hzwer.com

「BZOJ3698」「FJ2014集训」XWW的难题

分类目录

热门文章

Myfriends

近期评论