$n leq 40$个人玩$m leq 10$台游戏机，每台游戏机一秒内只能一人玩，每人一秒内只能玩一台。每台游戏机有个价格，在规定总价格内可以把一部分游戏机复制一次，每台只能复制一次。给每个人对在每台游戏机上的需求时间，求一种方案使得所有玩游戏结束的时间尽量早。每个人每台游戏需求时间$leq 2500$。
先不考虑复制。$R_i$表示人$i$玩游戏总时间，$C_j$表示机器$j$被玩总时间。可以发现答案的下界是$max(max(R_i),max(C_j))$，叫$T$。然后把人和机器建一个二分图，保证每个点的度数为$T$，就能在上面不停地做最大匹配，就可以把答案定为$T$。这里这么搞：左边$n$个人和$m$个假人，右边$m$台机器和$n$个假机器，假的东西用来补度数。然后，两边会连四种边：（1）真人真机器，连很多条边，边数为对应时间（其实可以连一条边记一个边权）；（2）假人真机器，如果那个机器的度数不到$T$，那它肯定有一段空闲时间为$T-C_j$，这么多条边连向他对应的假人；（3）真人假机器，同（2）；（4）假人假机器，这时假人和假机器的度数不到$T$，可以把真人真机器的图复制一遍把每个点度数补到$T$。把“连很多条边”搞成“连一条边，记个边权”，每次做完最大匹配后把所有边权减去匹配边中最小的那一个，然后把边权为0的边删掉。此时如果一条匹配边左右两边都是真人真机器，把这个操作记录下来，以此输出方案。
然后是钱的问题。当$T$为某个$C_j$时钱有用，此时若有钱就复制他，把机器的被玩时间均分成两份，使得$T$变小。
1 //#include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 //#include<time.h> 5 //#include<complex> 6 //#include<set> 7 //#include<queue> 8 //#include<vector> 9 #include<algorithm> 10 #include<stdlib.h> 11 using namespace std; 12 13 #define LL long long 14 int qread() 15 { 16 char c; int s=0,f=1; while ((c=getchar())<'0' || c>'9') (c=='-') && (f=-1); 17 do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s*f; 18 } 19 20 //Pay attention to '-' , LL and double of qread!!!! 21 22 int n,m,B; 23 int a[88],t[88][88],R[88],C[88]; bool co[88]; 24 struct Node{int a,b,c,d;}ans[1000011]; int lans=0; 25 26 struct BG 27 { 28 int mp[88][88],p[88],q[88],n; bool vis[88]; 29 void clear(int N) {n=N;} 30 bool Pei(int x) 31 { 32 vis[x]=1; 33 for (int i=1;i<=n;i++) if (mp[x][i] && !q[i]) 34 { 35 p[x]=i; q[i]=x; 36 return 1; 37 } 38 for (int i=1;i<=n;i++) if (mp[x][i] && q[i] && !vis[q[i]] && Pei(q[i])) 39 { 40 p[x]=i; q[i]=x; 41 return 1; 42 } 43 return 0; 44 } 45 void pei(int x) {memset(vis,0,sizeof(vis)); Pei(x);} 46 }g; 47 48 int main() 49 { 50 n=qread(); m=qread(); B=qread(); 51 for (int i=1;i<=m;i++) a[i]=qread(); 52 for (int i=1,x;i<=n;i++) 53 { 54 x=qread(); 55 for (int j=1,u,v;j<=x;j++) 56 { 57 u=qread(); v=qread(); 58 t[i][u]=v; 59 } 60 } 61 62 for (int i=1;i<=n;i++) 63 for (int j=1;j<=m;j++) 64 R[i]+=t[i][j],C[j]+=t[i][j]; 65 int T=0,maxr=0; 66 for (int i=1;i<=n;i++) maxr=max(maxr,R[i]); 67 for (int j=1;j<=m;j++) T=max(T,C[j]); T=max(T,maxr); 68 while (B) 69 { 70 int id=0; 71 for (int j=1;j<=m;j++) if (T==C[j] && co[j]) {id=-1; break;} 72 if (id==-1) break; 73 for (int j=1;j<=m;j++) if (T==C[j]) {id=j; break;} 74 if (!id) break; 75 if (a[id]>B) break; 76 77 int tot=T>>1; 78 for (int i=1;i<=n;i++) 79 { 80 if (tot<t[i][id]) {t[i][id+m]=tot; t[i][id]-=tot; break;} 81 else {tot-=t[i][id]; t[i][id+m]=t[i][id]; t[i][id]=0;} 82 } 83 84 co[id]=1; B-=a[id]; 85 C[id]=0; for (int i=1;i<=n;i++) C[id]+=t[i][id]; 86 C[id+m]=0; for (int i=1;i<=n;i++) C[id+m]+=t[i][id+m]; 87 T=0; for (int j=1;j<=m;j++) T=max(T,C[j]); T=max(T,maxr); 88 } 89 90 g.clear(n+m+m); 91 for (int i=1;i<=n;i++) 92 for (int j=1;j<=m+m;j++) if (t[i][j]) 93 g.mp[i][j]=g.mp[j+n][i+m+m]=t[i][j]; 94 for (int i=1;i<=n;i++) if (R[i]<T) g.mp[i][i+m+m]=T-R[i]; 95 for (int j=1;j<=m+m;j++) if (C[j]<T) g.mp[j+n][j]=T-C[j]; 96 97 98 printf("%d ",T); 99 for (int j=1;j<=m;j++) printf("%d",co[j]); puts(""); 100 lans=0; 101 for (int i=1;i<=n+m+m;i++) g.pei(i); 102 while (T) 103 { 104 int tmp=0x3f3f3f3f; 105 for (int i=1;i<=n+m+m;i++) tmp=min(tmp,g.mp[i][g.p[i]]); 106 for (int i=1;i<=n;i++) if (g.p[i]<=m+m) 107 ans[++lans]=(Node){i,g.p[i]<=m?g.p[i]:g.p[i]-m,T-tmp,tmp}; 108 for (int i=1;i<=n+m+m;i++) g.mp[i][g.p[i]]-=tmp; 109 for (int i=1;i<=n+m+m;i++) if (g.mp[i][g.p[i]]==0) {g.q[g.p[i]]=0; g.p[i]=0; g.pei(i);} 110 T-=tmp; 111 } 112 113 printf("%d ",lans); 114 for (int i=1;i<=lans;i++) printf("%d %d %d %d ",ans[i].a,ans[i].b,ans[i].c,ans[i].d); 115 return 0; 116 }