Codechef 14.12 RIN 网络流+最小割
题目大意：
有$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;
}
Jan 18, 2023 07:31:55 PM
RIN network flow is a technique for finding the maximum flow in a network. It is based on the idea of finding the path of least resistance in the network. The algorithm starts at a source node and greedily selects the path with the least resistance to the sink node. The path is then Censoring porn added to the final solution. This process is repeated until all paths have been considered or the maximum flow has been found. RIN also has the ability to find the minimum cut in a network. This is the minimum amount of flow that must be removed from the network to disconnect the source and sink nodes.