?

?

?

题意：M个猪圈，N个顾客，每个顾客有一些的猪圈的钥匙，只能购买能打开的猪圈里的猪，而且要买一定数量的猪，每个猪圈有已知数量的猪，
但是猪圈可以重新打开，将猪的个数，重新分配，但是只能将猪往当前打开状态的猪圈里赶，以达到卖出的猪的数量最多。

?

?

思路：还是4部分，源点->猪圈->猪圈->汇点

?

?

?

?

能用EK水的，当然用EK水

?

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #define init(a) memset(a,0,sizeof(a)) #define PI acos(-1,0) using namespace std; const int maxn = 500; const int maxm = 40000; #define lson left, m, id<<1 #define rson m+1, right, id<<1|1 #define min(a,b) (a>b)?b:a #define max(a,b) (a>b)?a:b #define MAX INT_MAX int c[1000][1000]; int re[1000]; int f[1000][1000]; int p[1000],n,m; void EK(int s,int t) { queue
         
          q; while(q.empty()==false) q.pop(); int sum = 0; while(1) { memset(re,0,sizeof(re)); q.push(s); re[s] = MAX; p[s] = -1; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = 1;i<=n+1;i++) { if(!re[i] && f[u][i] < c[u][i]) { q.push(i); p[i] = u; re[i] = min(re[u],c[u][i]-f[u][i]); } } } if(re[t]==0) break; for(int st = t;st!=s;st = p[st]) { f[p[st]][st] += re[t]; f[st][p[st]] -= re[t]; } sum += re[t]; } printf(%d ,sum); } void initt() { for(int i = 0;i<=n+1;i++) { for(int j = 0;j<=n+1;j++) { c[i][j] = f[i][j] = 0; } p[i] = 0; } } int main() { int pig[1001]; int a,b,w; while(~scanf(%d%d,&m,&n)) { initt(); for(int j = 1;j<=m;j++) scanf(%d,&pig[j]); for(int i = 1;i<=n;i++) { scanf(%d,&a); while(a--) { scanf(%d,&b); if(!p[b])//判断当前猪圈是否打开过 { c[p[b]][i] += pig[b]; p[b] = i; } else { c[p[b]][i] = MAX;//打开过说明，可以从其他猪圈流向本猪圈，流量可能为无限大 p[b] = i; } } scanf(%d,&w); c[i][n+1] += w; } EK(0,n+1); } return 0; } 
         
        
       
      
     
    
   
  

?