小R的烦恼
这题我看了好久都没看出来到底是一发什么题目，然后看了看路牌，哇费用流。
这题要把每一天看成两个点，一个是能用的研究生，一个是病倒的研究生，然后st，ed分别连向这两个点来严格限制流量，然后再根据医院，连病倒的到能用的一条边，最后跑一次费用流就OVER了。
|
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 99 100 |
#include<set> #include<map> #include<list> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define qread(x) x=read() #define mes(x,y) memset(x,y,sizeof(x)) #define mpy(x,y) memcpy(x,y,sizeof(x)) #define Maxn 52 #define INF 1073741824 inline int read(){ int f=1,x=0;char ch; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } struct Edge{ int x,y,d,c,next,other; }a[8*Maxn*Maxn+1];int len,first[2*Maxn+1]; void ins(int x,int y,int d,int c){ len++; a[len].x=x;a[len].y=y;a[len].d=d;a[len].c=c; a[len].next=first[x];first[x]=len;a[len].other=len+1; len++; a[len].x=y;a[len].y=x;a[len].d=0;a[len].c=-c; a[len].next=first[y];first[y]=len;a[len].other=len-1; } std::queue<int>q; bool v[2*Maxn+1]; int x,y,d[2*Maxn+1],pre[2*Maxn+1]; bool spfa(int st,int ed,int &flow,int &ans){ mes(d,63);d[ed]=INF;d[st]=0; mes(v,false);v[st]=true; q.push(st); while(q.empty()==false){ x=q.front();q.pop(); for(int k=first[x];k>0;k=a[k].next){ y=a[k].y; if(d[y]>d[x]+a[k].c&&a[k].d>0){ d[y]=d[x]+a[k].c; pre[y]=k; if(v[y]==false){ v[y]=true; q.push(y); } } } v[x]=false; } if(d[ed]==INF)return false; else{ x=pre[ed]; while(x>0){ a[x].d--;a[a[x].other].d++; x=pre[a[x].x]; } flow++; ans+=d[ed]; return true; } } int T,n,m,k,flow,ans,sum,st,ed; int main(){ qread(T); for(int t=1;t<=T;t++){ qread(n),qread(m),qread(k); st=2*n+1;ed=st+1; sum=0; len=0;mes(first,0); for(int i=1;i<=n;i++){ qread(x); ins(st,i+n,x,0); ins(i,ed,x,0); sum+=x; if(i!=n)ins(i,i+1,INF,0); } for(int i=1;i<=m;i++){ qread(x),qread(y); ins(st,1,x,y); } for(int i=1;i<=k;i++){ qread(x),qread(y); x++; for(int j=1;j<=n-x;j++)ins(j+n,j+x,INF,y); } ans=flow=0; while(spfa(st,ed,flow,ans)==true); printf("Case %d: ",t); if(flow==sum)printf("%d\n",ans); else printf("impossible\n"); } } |