#include<iostream> #include<stdio.h> #define MAXN 105 #include"queue" #define inf 10000000 #include<stdio.h> using namespace std; int max_flow_ljz(int n,int * * mat,int source,int sink,int * * flow); int main() { //freopen("acm.acm","r",stdin); int n_pig; int n_cust; int n_key; int tem; int i; int j; int * pig_house; int * pig_h_c; int * * _m; int * * f; cin>>n_pig>>n_cust; _m = new int * [n_cust + 2]; f = new int * [n_cust + 2]; for(i = 0; i < n_cust + 2; ++ i) { _m[i] = new int[n_cust + 2]; f[i] = new int[n_cust + 2]; memset(_m[i],0,sizeof(int)*(n_cust + 2)); } pig_house = new int[n_pig]; pig_h_c = new int[n_pig]; memset(pig_h_c,0,sizeof(int)*n_pig); for(i = 0; i < n_pig; ++ i) { cin>>tem; pig_house[i] = tem; } for(j = 1; j <= n_cust; ++ j) { cin>>n_key; for(i = 0; i < n_key; ++ i) { cin>>tem; if(pig_h_c[tem - 1] != 0) _m[pig_h_c[tem - 1]][j] = inf; else { _m[0][j] += pig_house[tem - 1]; pig_h_c[tem - 1] = j; } } cin>>tem; _m[j][n_cust+1] = tem; } cout<<max_flow_ljz(n_cust+2,_m,0,n_cust+1,f); } int max_flow_ljz(int n,int * * mat,int source,int sink,int * * flow){ int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j; if (source==sink) return inf; for (i=0;i<n;i++) for (j=0;j<n;flow[i][j++]=0); for (;;){ for (i=0;i<n;pre[i++]=0); pre[t=source]=source+1,d[t]=inf; for (p=q=0;p<=q&&!pre[sink];t=que[p++]) for (i=0;i<n;i++) if (!pre[i]&&(j=mat[t][i]-flow[t][i])) pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j; else if (!pre[i]&&(j=flow[i][t])) pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j; if (!pre[sink]) break; for (i=sink;i!=source;) if (pre[i]>0) flow[pre[i]-1][i]+=d[sink],i=pre[i]-1; else flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1; } for (j=i=0;i<n;j+=flow[source][i++]); return j; }
关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。
技术网站地址： vmfor.com