$$\sum_{j=1}^k b_j \geq a_i$$

$$\sum_{i=1}^m b_ic_i$$

$$\sum_{j=1}^k b_j – a_i – d_i=0$$

$a_1=5,a_2=4,a_3=3$

$$0=0$$

$$b_1+b_3-d_1-a_1=0$$

$$b_1+b_2+b_3-d_2-a_2=0$$

$$b_1+b_2-d_3-a_3=0$$

$$0=0$$

$$b_1+b_3-d_1-a_1=0$$

$$b_2+d_1-d_2+a_1-a_2=0$$

$$-b_3+d_2-d_3+a_2-a_3=0$$

$$-b_1-b_2+d_3+a_3=0$$

(我草稿本上有一个很可爱的图可惜学校没有手机拍不下来)(鸽子说: 回家再拍)

$qhy$作为老年退役猫咪刚开始是这样想的呢

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define edge(i, u) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
#define N 10005
#define inf 1023333333
int n, m, head[N], tot = 1, ans, que[N + 5], hh, tt, dis[N], pre[N], cap[N], a[N];
bool vis[N];
int sum;
struct edge{
int to, nxt, w, cap;
}e[N << 3];
inline void addedge (int u, int v, int w, int cap)
{
//    printf("u = %d  v = %d   w = %d   cap = %d \n", u, v, w, cap);
e[++tot] = (edge) {v, head[u], w, cap};
e[++tot] = (edge) {u, head[v], -w, 0};
}
inline bool spfa (int s, int t)
{
que[1] = s; vis[s] = 1;
hh = tt = 1;
fo (i, 0, n + 3)
{
dis[i] = inf;
cap[i] = inf;
}
dis[s] = 0;
while (hh != tt + 1)
{
int u = que[hh];
edge (i, u)
if (e[i].cap && dis[u] + e[i].w < dis[v])
{
pre[v] = i;
dis[v] = dis[u] + e[i].w;
cap[v] = std::min(cap[u], e[i].cap);
if (!vis[v])
{
vis[v] = 1;
tt++;
if (tt == N) tt -= N;
que[tt] = v;
}
}
vis[u] = 0;
hh++;
if (hh == N) hh -= N;
}
return dis[t] != inf;
}
inline void updata (int s, int t)
{
int i = t;
while (i != s)
{
e[pre[i]].cap -= cap[t];
e[pre[i] ^ 1].cap += cap[t];
i = e[pre[i] ^ 1].to;
}
ans += dis[t] * cap[t];
sum += cap[t];
}
inline void costflow (int s, int t)
{
while (spfa(s, t))
updata(s, t);
}
int main ()
{
int T;
scanf("%d", &T);
fo (qwq, 1, T)
{
memset(e, 0, sizeof e); tot = 1;
ans = sum = 0;
int psum = 0;
printf("Case #%d: ", qwq);
scanf("%d", &n);
int s = 0, t = n + 1;
fo (i, 2, n)
{
int u, v, p;
scanf("%d %d %d", &u, &v, &p);
psum += p;
}
scanf("%d", &m);
fo (i, 1, m)
{
int u, v, cap, c;
scanf("%d %d %d %d", &u, &v, &cap, &c);
}
costflow(s, t);
if (sum != psum)
printf("-1\n");
else
printf("%d\n", ans);
}
return 0;
}


1 条评论

Remmina · 2019年2月22日 12:02 上午

Mark 一下明天（严格来说是今天）学