测试地址：志愿者招募
做法：根据这位大牛的方法做的，看完之后觉得这题简直是神题啊！能想出来也是太强了。
好了废话不多说，这位大牛说的构图原理是非常清楚的，就是利用线性规划建立等式，化成只有一边为0的形式，然后把正的量看成流入的流量，把负的量看成流出的流量，就可以满足流量平衡，然后按照这些东西连边即可。
然而我们大可不必在程序里面把这些式子都推出来再建图，实际上我们可以发现，若把0和n+2看成附加源点和附加汇点，1~n+1看成上文中说的那些式子代表的顶点，我们可以发现规律：如果有一类志愿者从第a天到第b天工作，工资是c，那么根据推演之后一定是从顶点a到顶点b+1之间连一条容量无限，费用为c的边。这一步是连上了正负X变量所代表的边。下一步连正负Y变量所代表的边，可知就是在2到1,3到2，...，n+1到n之间连接一条容量无限，费用为0的边。唯一要算的就是上面这些式子的常数项，然后按文中的方法连接附加源点和附加汇点的边即可。最后对这个网络做一遍最小费用最大流，最小费用就是答案。
以下是本人代码：
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #define inf 1000000000 using namespace std; int n,m,p[1010][1010]={0},v[1010]={0},vp[1010]; int tot=1,first[1010]={0},dis[1010],maxf[1010],last[1010],laste[1010]; bool vis[1010]; struct edge {int v,f,c,next;} e[100010]; void insert(int a,int b,int f,int c) { e[++tot].v=b,e[tot].f=f,e[tot].c=c,e[tot].next=first[a],first[a]=tot; e[++tot].v=a,e[tot].f=0,e[tot].c=-c,e[tot].next=first[b],first[b]=tot; } bool spfa() { queue<int> q; for(int i=0;i<=n+2;i++) dis[i]=inf,maxf[i]=inf; memset(vis,0,sizeof(vis)); dis[0]=0;vis[0]=0; q.push(0); while(!q.empty()) { int v=q.front();q.pop(); for(int i=first[v];i;i=e[i].next) { if (e[i].f) { if (dis[e[i].v]>dis[v]+e[i].c) { dis[e[i].v]=dis[v]+e[i].c; maxf[e[i].v]=min(maxf[v],e[i].f); last[e[i].v]=v; laste[e[i].v]=i; if (!vis[e[i].v]) { vis[e[i].v]=1; q.push(e[i].v); } } } } vis[v]=0; } return dis[n+2]!=inf; } int mincost() { int cost=0; while(spfa()) { cost+=maxf[n+2]*dis[n+2]; int v=n+2; while(v) { e[laste[v]].f-=maxf[n+2]; e[laste[v]^1].f+=maxf[n+2]; v=last[v]; } } return cost; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&v[i]); for(int i=1,a,b,c;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); insert(a,b+1,inf,c); } for(int i=2;i<=n+1;i++) insert(i,i-1,inf,0); for(int i=n+1;i>=1;i--) { vp[i]=v[i]-v[i-1]; if (vp[i]>=0) insert(0,i,vp[i],0); else insert(i,n+2,-vp[i],0); } printf("%d",mincost()); return 0; }
