万年没更新的blog 终于更新一篇了。。。
看完题首先就会想到费用流，
重点是建图，发现可以把第i个位置看成第i天需要的减去第i-1天所需要的，那么如果这个值>=0就从s连过来，否则连向t。
把第i类人从u 连向 v+1即可。
最后跑费用流
c++代码如下：
[[......]
标签：最小费用最大流
1061: [Noi2008]志愿者招募
P3381 【模板】最小费用最大流
跑spfa，然后dfs一样的步骤，不过要注意 反向边费用取反。
c++代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #define rep(i,x,y) for(register int i = x ;i <= y;++i) using namespace std; template<typename T>void read(T&x) { char c;int sign = 1;x = 0; do { c = getchar();if(c == '-') sign = -1; }while(c < '0' || c >'9'); do { x = x * 10 + c - '0';c = getchar(); }while(c <= '9' && c >= '0'); x *= sign; } void print(int num) { if(num > 9) print(num/10); putchar(num%10 + '0'); } const int N = 5e3 + 50,M = 5e4 + 500,inf = 0x3f3f3f3f; int head[N],d[N],tot,res,ans,n,m,s,t; bool vis[N]; struct node { int next,flow,cup,to,w; }edge[M<<1]; inline void add(int a,int b,int val,int wi) { edge[tot].to = b; edge[tot].next = head[a]; edge[tot].flow = 0; edge[tot].cup = val; edge[tot].w = wi; head[a] = tot++; } bool bfs() { memset(d,0x3f,sizeof d); memset(vis,0,sizeof vis); queue<int>q; d[s] = 0;q.push(s); while(!q.empty()) { int x = q.front();q.pop();vis[x] = false; for(register int i = head[x];~i ;i = edge[i].next) { node&e = edge[i]; if(d[e.to] <= d[x] + e.w || e.cup <= e.flow) continue; d[e.to] = d[x] + e.w; if(!vis[e.to]) q.push(e.to),vis[e.to] = 1; } } if(d[t] < inf) return true; return false; } int dfs(int u,int w) { vis[u] = 1; if(u == t || w == 0) return w; int flow = 0,f; for(register int i = head[u];~i;i = edge[i].next) { node&e = edge[i]; if(!vis[e.to] && e.cup > e.flow && d[e.to] == d[u] + e.w && (f = dfs(e.to,min(e.cup-e.flow,w))) ) { e.flow += f;edge[i^1].flow -= f; flow += f; w-= f; } } return flow; } int main() { memset(head,-1,sizeof head); read(n);read(m);read(s);read(t); rep(i,1,m) { int u,v,w,f; read(u);read(v);read(w);read(f); add(u,v,w,f);add(v,u,0,-f); } while(bfs()) { int flow ; vis[t] = 1; while(vis[t]) memset(vis,0,sizeof vis); flow = dfs(s,inf); res += d[t] * flow; ans += flow; } print(ans);putchar(' ');print(res); return 0; } |