目前处于迷之TLE状态
-----6.21更新 已AC
3442: 学习小组
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 200 Solved: 87
Description
【背景】
坑校准备鼓励学生参加学习小组。
【描述】
共有n个学生，m个学习小组，每个学生有一定的喜好，只愿意参加其中的一些学习小组，但是校领导为学生考虑，规定一个学生最多参加k个学习小组。财务处的大叔就没那么好了，他想尽量多收钱，因为每个学生参加学习小组都要交一定的手续费，不同的学习小组有不同的手续费。然而，事与愿违，校领导又决定对学习小组组织者进行奖励，若有a个学生参加第i个学习小组，那么给这个学习小组组织者奖励Ci*a^2元。在参与学生（而不是每个学习小组的人数总和）尽量多的情况下，求财务处最少要支出多少钱（若为负数，则输出负数）（支出=总奖励费-总手续费）。
Input
输入有若干行，第一行有三个用空格隔开的正整数n、m、k。接下来的一行有m个正整数，表示每个Ci。第三行有m个正整数，表示参加每个学习小组需要交的手续费Fi。再接下来有一个n行m列的矩阵，表若第i行j列的数字是1，则表示第i个学生愿意参加第j个学习小组，若为0，则为不愿意。
Output
输出只有一个整数，为最小的支出。
Sample Input
3 3 1
1 2 3
3 2 1
111
111
111
Sample Output
-2
【样例解释】
参与学生最多为3，每个学生参加一个学习小组，若有两个学生参加第一个学习小组，一个学生参加第二个学习小组（一定要有人参加第二个学习小组），支出为-2，可以证明没有更优的方案了。
【数据范围与约定】
100%的数据，0＜n≤100，0＜m≤90，0＜k≤m，0＜Ci≤10，0＜Fi≤100。
HINT
Source
By lll6924 at “冬令营后竞速放松赛”
同一门课报的人数不同，费用也会变化，所以需要“拆边”，从小组结点向汇点连n条边，费用分别为第1、2、3....n个人报名的费用，容量均为1
参与同学要尽可能多，但每个同学不一定要报满，所以从每个学生结点向汇点连k-1条边（至少报1项），费用均为0
此处为第一版。更新版本见更下方
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<queue> 8 using namespace std; 9 const int INF=100000000; 10 const int mxn=150; 11 int n,m,k; 12 int c[mxn]; 13 int f[mxn]; 14 int ans=0; 15 //net 16 struct edge{ 17 int from,to,nx,v,c; 18 }e[mxn*500]; 19 int s,t; 20 int cnt=1; 21 int hd[mxn],dis[mxn],pr[mxn]; 22 bool inqu[mxn]; 23 // 24 void add_edge(int u,int t,int v,int c){ 25 e[++cnt]=(edge){u,t,hd[u],v,c};hd[u]=cnt; 26 e[++cnt]=(edge){t,u,hd[t],0,-c};hd[t]=cnt; 27 return ; 28 } 29 bool SPFA(){ 30 int i,j; 31 queue<int>q; 32 memset(inqu,false,sizeof(inqu)); 33 for(i=0;i<=t;i++)dis[i]=INF; 34 dis[s]=0; 35 q.push(s); 36 inqu[s]=true; 37 while(!q.empty()){ 38 int u=q.front(); 39 inqu[u]=false; 40 q.pop(); 41 for(i=hd[u];i;i=e[i].nx){ 42 int v=e[i].to; 43 if(e[i].v && dis[u]+e[i].c<dis[v]){ 44 dis[v]=dis[u]+e[i].c; 45 pr[v]=i; 46 if(!inqu[v]){ 47 inqu[v]=true; 48 q.push(v); 49 } 50 } 51 } 52 } 53 return dis[t]!=INF; 54 } 55 void mcf(){ 56 int i,j; 57 while(SPFA()){ 58 int tmp=INF; 59 for(i=pr[t];i;i=pr[e[i].from]) 60 tmp=min(tmp,e[i].v); 61 ans+=tmp*dis[t]; 62 for(i=pr[t];i;i=pr[e[i].from]){ 63 e[i].v-=tmp; 64 e[i^1].v+=tmp; 65 } 66 } 67 return; 68 } 69 int main(){ 70 scanf("%d%d%d",&n,&m,&k); 71 int i,j; 72 for(i=1;i<=m;i++)scanf("%d",&c[i]); 73 for(i=1;i<=m;i++)scanf("%d",&f[i]); 74 char ch[100]; 75 for(i=1;i<=n;i++){ 76 scanf("%s",ch); 77 for(j=1;j<=m;j++){ 78 if(ch[j-1]=='1') add_edge(i,j+n,1,0); 79 } 80 } 81 s=0;t=n+m+1; 82 for(i=1;i<=n;i++){ 83 add_edge(s,i,k,0); 84 add_edge(i,t,k-1,0);//留出空边(并不是所有人都要排满课 ) 85 } 86 for(i=1;i<=m;i++) 87 for(j=1;j<=n;j++){ 88 add_edge(i+n,t,1,(2*j-1)*c[i]-f[i]); 89 //拆边，每多一个人报课，支出增长 90 } 91 mcf(); 92 printf("%d\n",ans); 93 return 0; 94 }
AC
各种缩小数组范围，加上inline和手动read，甚至用上了HK_reporter玄学加成，仍然TLE
最后的最后，FXXK，发现原来是数组开小了
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<queue> 8 9 #define HK_reporter main 10 using namespace std; 11 const int INF=100000000; 12 const int mxn=320; 13 int n,m,k; 14 int c[mxn]; 15 int f[mxn]; 16 int ans=0; 17 //net 18 struct edge{ 19 int from,to,nx,v,c; 20 }e[mxn*400]; 21 int s,t; 22 int cnt=1; 23 int hd[mxn],dis[mxn],pr[mxn]; 24 bool inqu[mxn]; 25 // 26 inline int read(){ 27 int x=0;char ch=getchar(); 28 while(ch<'0' ||ch>'9')ch=getchar(); 29 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 30 return x; 31 } 32 inline void add_edge(int u,int t,int v,int c){ 33 e[++cnt]=(edge){u,t,hd[u],v,c};hd[u]=cnt; 34 e[++cnt]=(edge){t,u,hd[t],0,-c};hd[t]=cnt; 35 return ; 36 } 37 bool SPFA(){ 38 int i; 39 queue<int>q; 40 memset(inqu,false,sizeof(inqu)); 41 for(i=0;i<=t;i++)dis[i]=INF; 42 dis[s]=0; 43 q.push(s); 44 inqu[s]=true; 45 while(!q.empty()){ 46 int u=q.front(); 47 inqu[u]=false; 48 q.pop(); 49 for(i=hd[u];i;i=e[i].nx){ 50 int v=e[i].to; 51 if(e[i].v && dis[u]+e[i].c<dis[v]){ 52 dis[v]=dis[u]+e[i].c; 53 pr[v]=i; 54 if(!inqu[v]){ 55 inqu[v]=true; 56 q.push(v); 57 } 58 } 59 } 60 } 61 return dis[t]!=INF; 62 } 63 void mcf(){ 64 int i,j; 65 while(SPFA()){ 66 int tmp=INF; 67 for(i=pr[t];i;i=pr[e[i].from]) 68 tmp=min(tmp,e[i].v); 69 ans+=tmp*dis[t]; 70 for(i=pr[t];i;i=pr[e[i].from]){ 71 e[i].v-=tmp; 72 e[i^1].v+=tmp; 73 } 74 } 75 return; 76 } 77 int HK_reporter(){ 78 n=read();m=read();k=read(); 79 int i,j; 80 for(i=1;i<=m;i++)c[i]=read(); 81 for(i=1;i<=m;i++)f[i]=read(); 82 char ch[100]; 83 for(i=1;i<=n;i++){ 84 scanf("%s",ch+1); 85 for(j=1;j<=m;j++){ 86 if(ch[j]=='1') add_edge(i,j+n,1,0); 87 } 88 } 89 s=0;t=n+m+1; 90 for(i=1;i<=n;i++){ 91 add_edge(s,i,k,0); 92 add_edge(i,t,k-1,0);//留出空边(并不是所有人都要排满课 ) 93 } 94 for(i=1;i<=m;i++) 95 for(j=1;j<=n;j++){ 96 add_edge(i+n,t,1,(2*j-1)*c[i]-f[i]); 97 //拆边，每多一个人报课，支出增长 98 } 99 mcf(); 100 printf("%d\n",ans); 101 return 0; 102 }
