本题和上题bzoj1221是很类似的啊
注意的是要为每个学校开一个新点，再流向另一边。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int inf=999999999; int n; struct node { int x,y,c,d,next,other; }a[2100000];int len,last[21000]; void ins(int x,int y,int c,int d) { int k1,k2; len++;k1=len; a[len].x=x;a[len].y=y;a[len].c=c;a[len].d=d; a[len].next=last[x];last[x]=len; //printf("%d %d %d %d ",x,y,c,d); len++;k2=len; a[len].x=y;a[len].y=x;a[len].c=0;a[len].d=-d; a[len].next=last[y];last[y]=len; a[k1].other=k2; a[k2].other=k1; } int C,ans,st,ed; int list[21000];bool v[21000]; int d[21000],pre[21000],cc[21000]; bool spfa() { memset(d,63,sizeof(d));d[st]=0; memset(cc,0,sizeof(cc));cc[st]=inf; memset(v,false,sizeof(v));v[st]=true; int head=1,tail=2;list[1]=st; while(head!=tail) { int x=list[head]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(d[y]>d[x]+a[k].d&&a[k].c>0) { d[y]=d[x]+a[k].d; cc[y]=min(cc[x],a[k].c); pre[y]=k; if(v[y]==false) { v[y]=true; list[tail]=y; tail++;if(tail==20500)tail=1; } } } v[x]=false; head++;if(head==20500)head=1; } if(d[ed]>=inf)return false; else { C+=cc[ed]; ans+=cc[ed]*d[ed]; int y=ed; while(pre[y]!=0) { int k=pre[y]; a[k].c-=cc[ed]; a[a[k].other].c+=cc[ed]; y=a[k].x; } return true; } } int main() { int T; scanf("%d",&T); for(int ttt=1;ttt<=T;ttt++) { int m,k,x,y,sum=0; scanf("%d%d%d",&n,&m,&k);st=n*2+m+1,ed=n*2+m+2; len=0;memset(last,0,sizeof(last)); for(int i=1;i<=n;i++) { scanf("%d",&x); ins(st,i,x,0); ins(i+n,ed,x,0); sum+=x; } for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); ins(st,2*n+i,x,0); for(int j=1;j<=n;j++)ins(2*n+i,j+n,x,y); } for(int i=1;i<=k;i++) { scanf("%d%d",&x,&y); for(int j=1;j<=n;j++) if(j+x+1<=n)ins(j,j+n+x+1,inf,y); else break; } for(int i=1;i<n;i++)ins(i,i+1,inf,0); C=0;ans=0; while(spfa()==true); printf("Case %d: ",ttt); if(C==sum)printf("%d ",ans); else printf("impossible "); } return 0; }