「湖北省队互测day6」Asiram

2015年1月4日3,7960

2.1 题目描述

Asiram 是个可爱的男孩子, 而现在, 他想给他的妹子Ecila 买制作人偶的材料.

这时候, 他发现, 在可选的n 种材料之中, 两种材料之间的搭配, 有的会显得很漂亮, 而有的就显得不那么漂亮, 还有的不影响总体的美观程度.

为了量化两种材料之间的搭配的漂亮程度,Asiram 设置了一个“美观度”. 同时, 每种材料还有一定的价格,Asiram 并不是想用有限的金钱去实现尽量大的美观度, 而是希望他的每一分钱都能带来尽量大的美观度, 即,使美观度与花费的比值尽量大.

2.2 输入格式

输入第一行为两个整数n 和m

下面1 行, 有n 个整数, 第i 个数为材料i 的价格wi

再下面m 行, 每行三个整数a; b; v, 即材料a 与材料b 的搭配能带来v 的美观度

2.3 输出格式

一行一个浮点数, 表示美观度与价格的比值的最大值, 当你的输出与标答之间的相对误差小于10^ – 6 时即被判为正确.

2.4 样例输入

5 6

1 1 1 1 1

1 2 1

1 4 1

2 3 1

2 4 1

3 4 1

3 5 1

2.5

样例输出

1.25000000

2.6 样例解释

购买材料1,2,3,4 制作人偶是一种最优方案, 花费4 而能带来5 的美观

度, 比值为1.25.

2.7 数据范围

对于10% 的数据,n<=5,1<=m<=10

对于40% 的数据,n<=50,1<=m<=500

对于100% 的数据,n<=500,1<=m<=5000,0 < wi,vi<=100

最大密度子图模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt,S,T;
int a[505],w[5005],u[5005],v[5005];
int cur[6005],last[6005],h[6005],q[6005],d[6005];
struct edge{
	int to,next;double v;
}e[50005];
void insert(int u,int v,double w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;
}
bool bfs()
{
	int head=0,tail=1;
	memset(h,-1,sizeof(h));
	q[0]=S;h[S]=0;
	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[T]!=-1;
}
double dfs(int x,double f)
{
	if(x==T)return f;
	double w,used=0;
	for(int i=cur[x];i;i=e[i].next)
		if(h[e[i].to]==h[x]+1)
		{
			w=dfs(e[i].to,min(f-used,e[i].v));
			e[i].v-=w;e[i^1].v+=w;
			if(e[i].v)cur[x]=i;
			used+=w;if(used==f)return f;
		}
	if(!used)h[x]=-1;
	return used;
}
double dinic()
{
	double tmp=0;
	while(bfs())
	{
		for(int i=S;i<=T;i++)cur[i]=last[i];
		tmp+=dfs(S,inf);
	}
	return tmp;
}
bool jud(double mid)
{
	cnt=1;memset(last,0,sizeof(last));
	double tot=0;
	for(int i=1;i<=m;i++)
	{
		insert(0,i,w[i]);
		tot+=w[i];
	}
	for(int i=1;i<=m;i++)
	{
		insert(i,v[i]+m,inf);
		insert(i,u[i]+m,inf);
	}
	for(int i=1;i<=n;i++)
		insert(m+i,T,a[i]*mid);
	return tot-dinic()>0;
}
int main()
{
	n=read();m=read();T=n+m+1;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=m;i++)
		u[i]=read(),v[i]=read(),w[i]=read();
	double l=0,r=100;
	for(int i=1;i<=100;i++)
	{
		double mid=(l+r)/2;
		if(jud(mid))l=mid;
		else r=mid;
	}
	printf("%.8lf",l);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,cnt,S,T;

int a[505],w[5005],u[5005],v[5005];

int cur[6005],last[6005],h[6005],q[6005],d[6005];

struct edge{

int to,next;double v;

}e[50005];

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

{

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

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

}

bool bfs()

{

int head=0,tail=1;

memset(h,-1,sizeof(h));

q[0]=S;h[S]=0;

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[T]!=-1;

}

double dfs(int x,double f)

{

if(x==T)return f;

double w,used=0;

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

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

{

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

e[i].v-=w;e[i^1].v+=w;

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

used+=w;if(used==f)return f;

}

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

return used;

}

double dinic()

{

double tmp=0;

while(bfs())

{

for(int i=S;i<=T;i++)cur[i]=last[i];

tmp+=dfs(S,inf);

}

return tmp;

}

bool jud(double mid)

{

cnt=1;memset(last,0,sizeof(last));

double tot=0;

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

{

insert(0,i,w[i]);

tot+=w[i];

}

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

{

insert(i,v[i]+m,inf);

insert(i,u[i]+m,inf);

}

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

insert(m+i,T,a[i]*mid);

return tot-dinic()>0;

}

int main()

{

n=read();m=read();T=n+m+1;

for(int i=1;i<=n;i++)a[i]=read();

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

u[i]=read(),v[i]=read(),w[i]=read();

double l=0,r=100;

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

{

double mid=(l+r)/2;

if(jud(mid))l=mid;

else r=mid;

}

printf("%.8lf",l);

return 0;

}

« 「BZOJ2756」[SCOI2012] 奇怪的游戏「BZOJ2095」[POI2010] Bridges »

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

「湖北省队互测day6」Asiram

分类目录

热门文章

Myfriends

近期评论