# bzoj 4108 [Wf2015]Catering

1 1

10

10

n, k <= 100;

### 题解

s->1,[0,k],0
1->xi,[0,inf],0
yi->t,[0,inf],0
xi->yi,[1,1],0

yi->xj,[0,inf],c

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 30010
#define inf 0x33333333
using namespace std;
typedef pair<int, int> Pair;
struct MFMC {
struct node {
int from, to, next, flow, cost;
}e[N];
int tot, st[N], pe[N], pv[N], dis[N], vis[N];
void init() {
tot = -1, memset(e, -1, sizeof e);
memset(st, -1, sizeof st);
}
void add(int x, int y, int z, int zz) {
e[++tot].to = y, e[tot].from = x;
e[tot].flow = z, e[tot].cost = zz;
e[tot].next = st[x], st[x] = tot;
}
void add_edge(int x, int y, int z, int zz) {
}
queue <int> que;
bool spfa(int S, int T) {
memset(dis, 0x33, sizeof dis);
memset(vis, 0, sizeof vis);
que.push(S), vis[S] = 1, dis[S] = 0;
while(!que.empty()) {
int now = que.front();
que.pop();
vis[now] = 0;
for (int i = st[now]; ~i; i = e[i].next)
if (e[i].flow > 0 && dis[e[i].to] > dis[now] + e[i].cost) {
dis[e[i].to] = dis[now] + e[i].cost;
pe[e[i].to] = i, pv[e[i].to] = now;
if (!vis[e[i].to])
vis[e[i].to] = 1, que.push(e[i].to);
}
}
return dis[T] < inf;
}
Pair mfmc(int S, int T) {
int COST = 0, FLOW = 0, flow;
while(spfa(S, T)) {
flow = inf;
for (int i = T; i != S; i = pv[i])
flow = min(flow, e[pe[i]].flow);
COST += flow * dis[T];
FLOW += flow;
for (int i = T; i != S; i = pv[i])
e[pe[i]].flow -= flow, e[pe[i] ^ 1].flow += flow;
}
return make_pair(FLOW, COST);
}
}mcmf;
int n, m, x, y, z, k, d[N];
int main() {
int S, T, s, t;
mcmf.init();
scanf("%d%d", &n, &k);
s = 1, t = n * 2 + 3, S = t + 1, T = S + 1;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n + 1; ++j)
scanf("%d", &x), mcmf.add_edge(i + n + 1, j, inf, x);
mcmf.add_edge(s, 1 + n + 1, k, 0);
for (int i = 2; i <= n + 1; ++i)
d[i]--, d[n + i + 1]++,
mcmf.add_edge(n + 1 + i, t, inf, 0);
for (int i = 1; i <= t; ++i)
if (d[i] > 0)