【SDOI2015】星际战争

#include<cstdio>

#include<queue>

using namespace std;

const int M = 10000;

const double inf = 1e18;

int n , m , h[505] , cur[505] , dep[505] , s , t , tot = 1;

double a[55] , b[55] , ans , Max;

struct edge{

	int to , nxt;

	double w;

}e[M + 5] , ee[M + 5];

inline double min(double x , double y) {return x < y ? x : y;};

inline void add(int x , int y , double w)

{

	e[++tot].to = y;

	e[tot].w = w;

	e[tot].nxt = h[x];

	h[x] = tot;

}

inline int bfs(int s , int t)

{

	for(register int i = s; i <= t; i++) dep[i] = 0 , cur[i] = h[i];

	queue<int> Q;

	dep[s] = 1;

	Q.push(s);

	while (!Q.empty())

	{

		int now = Q.front();

		Q.pop();

		for(register int i = h[now]; i; i = ee[i].nxt)

		{

			int v = ee[i].to;

			if (ee[i].w <= 0 || dep[v] != 0) continue;

			dep[v] = dep[now] + 1;

			Q.push(v);

		}

	}

	return dep[t];

}

inline double dfs(int x , int fa , double mi)

{

	if (x == t || mi <= 0) return mi;

	double flow = 0;

	for(register int i = cur[x]; i; i = ee[i].nxt)

	{

		cur[x] = i;

		int v = ee[i].to;

		if (v == fa || dep[x] + 1 != dep[v] || ee[i].w <= 0) continue;

		double f = dfs(v , x , min(mi , ee[i].w));

		if (f <= 0) continue;

		mi -= f , ee[i].w -= f , ee[i ^ 1].w += f , flow += f;

		if (mi <= 0) break;

	}

	return flow;

}

inline bool check(double mid)

{

	for(register int i = 1; i <= tot; i++) ee[i] = e[i];

	for(register int i = h[s]; i; i = ee[i].nxt)

		ee[i].w = b[ee[i].to] * mid;

	double res = 0;

	while (bfs(s , t)) res += dfs(s , 0 , inf);

	return res >= Max;

}

int main()

{

//	freopen("星际战争.in" , "r" , stdin);

	scanf("%d%d" , &n , &m);

	t = n + m + 5;

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

	{

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

		Max += a[i];

		add(i + m , t , a[i]);

		add(t , i + m , 0);

	}

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

	{

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

		add(s , i , b[i]);

		add(i , s , 0);

	}

	int x;

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

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

		{

			scanf("%d" , &x);

			if (x == 1) add(i , j + m , inf) , add(j + m , i , 0);

		}

	double l = 0 , r = 1e9 , mid;

	for(register int i = 1; i <= 60; i++)

	{

		mid = (l + r) * 0.5;

		if (check(mid)) r = mid , ans = mid;

		else l = mid;

	}

	printf("%.6lf" , ans);

}
巴特西

【SDOI2015】星际战争

最新文章

热门文章
