题目大意：一个项目需要N天才能完成，其中第i天需要Ai个人，共有M类志愿者可以招募，每种都有固定的工作时间和招募费用。找出一种最优的招募方案。
分析：其实这题很明显网络流，不过建图真的很麻烦很麻烦，要用到等式转换什么的，我就不献丑了，题解见 http://www.byvoid.com/blog/noi-2008-employee/
NOI要是真出个让你看出来是网络流的题，估计是没几个人能构出图来的...
代码真心丑，不过还是贴出来防丢：
View Code #include#include #include #include #include using namespace std; #define MaxN 1010 #define MaxM 10010 #define INF 20000000 struct edge { int y,x,next,op,flow,cost; }e[MaxM*4];int first[MaxN]; int n,m,tot=0,s,t,ans=0; int need[MaxN]; bool b[MaxN]; int d[MaxN],pre[MaxN]; queue q; void add(int x,int y,int cost,int flow=INF) { tot++; e[tot].y=y; e[tot].x=x; e[tot].flow=flow; e[tot].cost=cost; e[tot].op=tot+1; e[tot].next=first[x]; first[x]=tot; tot++; e[tot].y=x; e[tot].x=y; e[tot].flow=0; e[tot].cost=-cost; e[tot].op=tot-1; e[tot].next=first[y]; first[y]=tot; } void init() { int x,y,z; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&need[i]); for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y+1,z); } s=0;t=n+2; for (int i=1;i<=n+1;i++) { x=need[i]-need[i-1]; if (x>=0) add(s,i,0,x); else add(i,t,0,-x); if (i>1) add(i,i-1,0); } } bool spfa() { memset(d,100,sizeof(d)); memset(b,false,sizeof(b)); int MaxFlow=d[0],u; pre[s]=-1; d[s]=0;b[s]=true;q.push(s); while (!q.empty()) { u=q.front(); for (int p=first[u];p;p=e[p].next) { if (d[e[p].y]>d[u]+e[p].cost && e[p].flow) { pre[e[p].y]=p; d[e[p].y]=d[u]+e[p].cost; if (!b[e[p].y]) { b[e[p].y]=true; q.push(e[p].y); } } } b[u]=false; q.pop(); } if (d[t]