1 #include
     
        2 #include
      
         3 #include
       
          4 #define M 10000  5 #define inf 2139062143  6 using namespace std;  7 int cnt=1,n,m,T,d[M],q[2*M],f[M],head[M],next[10*M],u[10*M],v[10*M],w[10*M],fro[10*M],fr[M];  8 int mp[100];  9 long long ans; 10 void jia1(int a1,int a2,int a3,int a4) 11 { 12     cnt++; 13     next[cnt]=head[a1]; 14     head[a1]=cnt; 15     fro[cnt]=a1; 16     u[cnt]=a2; 17     v[cnt]=a3; 18     w[cnt]=a4; 19 } 20 void jia(int a1,int a2,int a3,int a4) 21 { 22     jia1(a1,a2,a3,a4); 23     jia1(a2,a1,0,-a4); 24     return; 25 } 26 bool spfa() 27 { 28     memset(d,127,sizeof(int)*(T+1)); 29     d[0]=0; 30     f[0]=1; 31     q[1]=0; 32     int h=0,t=1; 33     for(;h
        
         d[p]+w[i]) 40             { 41                 d[u[i]]=d[p]+w[i]; 42                 fr[u[i]]=i; 43                 if(!f[u[i]]) 44                   { 45                     f[u[i]]=1; 46                     t++; 47                     q[t]=u[i]; 48                     } 49             } 50       } 51     if(d[T]!=inf) 52       return 1; 53     return 0; 54 } 55 void mcf() 56 { 57     int mx=inf; 58     for(int i=fr[T];i;i=fr[fro[i]]) 59       mx=min(mx,v[i]); 60     for(int i=fr[T];i;i=fr[fro[i]]) 61       { 62         v[i]-=mx; 63         v[i^1]+=mx; 64         ans+=mx*w[i]; 65       } 66     return; 67 } 68 int main() 69 { 70     scanf("%d%d",&n,&m); 71     T=n+m+1; 72     for(int i=1;i<=m;i++) 73       { 74         int a1; 75         scanf("%d",&a1); 76         jia(n+i,T,a1,0); 77       } 78     for(int i=1;i<=n;i++) 79       for(int j=1;j<=m;j++) 80         { 81             int a1; 82             scanf("%d",&a1); 83             if(a1) 84               jia(i,n+j,inf,0); 85         } 86     for(int i=1;i<=n;i++) 87       { 88         int si; 89         scanf("%d",&si); 90         for(int j=1;j<=si;j++) 91           scanf("%d",&mp[j]); 92         mp[si+1]=inf; 93         for(int j=1;j<=si+1;j++) 94           { 95             int a1; 96             scanf("%d",&a1); 97             jia(0,i,mp[j]-mp[j-1],a1); 98           } 99       }100     for(;spfa();)101       mcf();102     printf("%lld\n",ans);103     return 0;104 }
        
       
      
     

按分段函数拆点跑费用流。