Codechef 12.4 CONNECT 随机化+斯坦纳树
Codechef 14.9 QRECT CDQ分治+分治+线段树

Codechef 14.12 RIN 网络流+最小割

shinbokuow posted @ Dec 02, 2015 08:51:41 PM in Something with tags 网络流 最小割 , 826 阅读

 

题目大意:
有$n$个课程,$m$个学期,每个课程都必须选择在某个学期学习,第$i$个课程在第$j$个学期学习将会得到$X_{i,j}$的价值。同时有$k$个限制条件,第$i$个限制条件给定$A_{i},B_{i}$,要求课程$A_{i}$所在的学期必须在$B_{i}$所在的学期之前。
求所有课程价值的最大平均值。
数据范围$n,m,k\leq{100}$,$0\leq{X_{i,j}}\leq{100}$,保证至少存在一种合法的解。
算法讨论:
将每个课程拆成一条长度为$m+1$的链,分别表示第$0-m$个学期,对于课程$i$,第$j-1(1\leq{j}\leq{m})$个点到第$j$个点连一条边,容量为$100-X_{i,j}$。
对于源点,连向所有链的第$0$个学期,容量为$\infty$。
所有链的第$m$个学期连向汇点,容量为$\infty$。
对于限制$A,B$,对于$1\leq{i}\leq{m}$,从$A$链的第$i-1$个学期连向$B$链的第$i$个学期,容量为$\infty$,这样就能满足题目中的限制了。
于是我们求最小割,再用$100\times{n}$减去就是最大的总和了。
再除以$n$就是最大平均值。
时空复杂度:
时间复杂度$O(MaxFlow(n\times{m},(n+k)\times{m}))$,空间复杂度$O((n+k)\times{m})$。
代码:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;

#define inf 0x3f3f3f3f
struct Solver {
	static const int V = 100010;
	static const int E = 1000010;
	int head[V], nxt[E], flow[E], to[E], ind, d[V];
	void reset() {
		ind = 0;
		memset(head, -1, sizeof head);
	}
	void addedge(int a, int b, int c) {
		int q = ind++;
		to[q] = b;
		nxt[q] = head[a];
		head[a] = q;
		flow[q] = c;
	}
	void make(int a, int b, int c) {
		addedge(a, b, c);
		addedge(b, a, 0);
	}
	bool bfs(int s, int t, int l, int r) {
		static int q[V], fr, ta, i, j;
		for (i = l; i <= r; ++i)
			d[i] = -1;
		fr = ta = 0;
		d[q[ta++] = s] = 0;
		while (fr != ta) {
			i = q[fr++];
			for (j = head[i]; j != -1; j = nxt[j])
				if (flow[j] && d[to[j]] == -1)
					d[q[ta++] = to[j]] = d[i] + 1;
		}
		return d[t] != -1;
	}
	int dinic(int p, int t, int Maxflow) {
		if (p == t)
			return Maxflow;
		int last = Maxflow;
		for (int j = head[p]; j != -1; j = nxt[j]) {
			if (flow[j] && d[to[j]] == d[p] + 1) {
				int toflow = dinic(to[j], t, last > flow[j] ? flow[j] : last);
				if (toflow) {
					flow[j] -= toflow;
					flow[j ^ 1] += toflow;
					if (!(last -= toflow))
						return Maxflow;
				}
			}
		}
		d[p] = -1;
		return Maxflow - last;
	}
	int Maxflow(int s, int t, int l, int r) {
		int ans = 0;
		while (bfs(s, t, l, r))
			ans += dinic(s, t, inf);
		return ans;
	}
}g;

int node[110][110];
int main() {
	int n, m, k, x, a, b;
	cin >> n >> m >> k;
	int i, j, id = 0;
	for (i = 1; i <= n; ++i)
		for (j = 0; j <= m; ++j)
			node[i][j] = ++id;
	g.reset();
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= m; ++j) {
			cin >> x;
			if (x == -1)
				g.make(node[i][j - 1], node[i][j], inf);
			else
				g.make(node[i][j - 1], node[i][j], 100 - x);
		}
	}
	int s = 0, t = ++id;
	for (i = 1; i <= n; ++i) {
		g.make(s, node[i][0], inf);
		g.make(node[i][m], t, inf);
	}
	while (k--) {
		cin >> a >> b;
		for (i = 1; i <= m; ++i)
			g.make(node[a][i - 1], node[b][i], inf);
	}
	
	printf("%.2lf\n", (n * 100 - g.Maxflow(s, t, 0, id)) / (double)n);
	
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter