第一题：按顾客访问猪圈的顺序依次构图（顾客为结点），汇点->第一个顾客->第二个顾客->...->汇点
//第一道网络流
//Ford-Fulkerson
//Time:47Ms Memory:276K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std; #define MAXN 105 //顾客
#define MAXM 1005 //猪圈
#define INF 0x3f3f3f3f struct Arc {
int c, f;
}e[MAXN][MAXN]; int n, m;
int s, t;
int pig[MAXM], last[MAXM]; //last[]:猪圈当前顾客(0为源点，n+1为汇点)
int pre[MAXN]; //1.从哪一个结点
int alpha[MAXN]; //2.可改进量 void ford() //ford fulkerson
{
alpha[s] = INF; //源点可改进量无限
while (1) { //多次标号
memset(pre, -1, sizeof(pre)); //初始标号
queue<int> q;
q.push(s);
while (!q.empty() && pre[t] == -1) {
int cur = q.front(); q.pop();
for (int i = 1; i <= t; i++)
{
int tmp;
//tmp 为非0可保证邻接且保证有剩余流量
if (pre[i] == -1 && (tmp = e[cur][i].c - e[cur][i].f))
{
pre[i] = cur;
q.push(i);
alpha[i] = min(alpha[cur], tmp);
}
}
}
if (pre[t] == -1) return; //未找到增广路
for (int i = pre[t], j = t; i != -1; j = i, i = pre[i])
{
e[i][j].f += alpha[t];
e[j][i].f = -e[i][j].f;
}
} } int main()
{
//freopen("in.txt", "r", stdin); memset(last, 0, sizeof(last));
memset(e, 0, sizeof(e));
scanf("%d%d", &m, &n);
s = 0; t = n + 1;
for (int i = 1; i <= m; i++)
scanf("%d", &pig[i]);
for (int i = 1; i <= n; i++)
{
int num; //钥匙数
scanf("%d", &num);
while (num--) {
int pn;
scanf("%d", &pn);
if (last[pn] == 0)
e[last[pn]][i].c += pig[pn];
else e[last[pn]][i].c = INF;
last[pn] = i;
}
scanf("%d", &e[i][t].c);
} ford(); int maxFlow = 0;
for (int i = 1; i < t; i++)
maxFlow += e[i][t].f;
printf("%d\n", maxFlow); return 0;
}
第二道：最短增广路(SAP)算法，dinic算法前身，与dinic不同的是需要多次采用BFS进行构建层次网络，题目本身较直接。
//网络流
//一般最短增广路算法-Dinic算法的前身
//Time:16Ms Memory:676K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std; #define MAX 205
#define INF 0x3f3f3f3f struct Arc {
int c, f;
}e[MAX][MAX]; int n, m;
int s, t;
int pre[MAX];
int res[MAX][MAX]; //残留网络->层次网络
bool v[MAX]; void bfs()
{
while (1) //多次BFS寻找增广路
{
memset(v, false, sizeof(v));
memset(res, 0, sizeof(res));
memset(pre, 0, sizeof(pre));
queue<int> q;
q.push(s); v[s] = true;
while (!q.empty() && pre[t] == 0)
{ //BFS构造层次网络
int cur = q.front(); q.pop();
for (int i = 1; i <= n; i++)
{
if (!v[i]) {
int tmp = e[cur][i].c - e[cur][i].f;
if (tmp > 0) { //正向有残留容量
res[cur][i] = tmp;
pre[i] = cur;
q.push(i); v[i] = true;
}
else if (e[i][cur].f > 0) { //反向有流量
res[cur][i] = e[i][cur].f;
pre[i] = cur;
q.push(i); v[i] = true;
}
}
}
}
if (pre[t] == 0) return;
int minroad = INF; //最小可改进量
for (int i = t; i != s; i = pre[i])
minroad = min(minroad, res[pre[i]][i]);
for (int i = t; i != s; i = pre[i])
{
if (e[pre[i]][i].c - e[pre[i]][i].f > 0)
e[pre[i]][i].f += minroad;
else if (e[i][pre[i]].f > 0)
e[i][pre[i]].f -= minroad;
} }
} int main()
{
//freopen("in.txt", "r", stdin); while (~scanf("%d%d", &m, &n))
{
memset(e, 0, sizeof(e));
int u, v, c;
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &u, &v, &c);
e[u][v].c += c;
} s = 1; t = n;
bfs(); int maxFlow = 0;
for (int i = 1; i < n; i++)
maxFlow += e[i][t].f;
printf("%d\n", maxFlow);
} return 0;
}