?

?

题意：为m个点，a个发电站，b个用户，n条边；然后是n条边u->v的容量；a个发电站u能提供的最大流量；b个个用户v能接受的最大流量。

思路： 最大网络流中多源多汇的问题，在图中添加1个源点Source和汇点Sink，将Soutce和每个发电站相连，容量是发电站能提供的最大流量；将每个用户和Sink相连，容量是每个用户能接受的最大流量。转化为最大流问题，然后求解。

?

注意输入格式就行，还是ISAP

?

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         const int N = 210; const int maxn = 300; const int maxm = 40000; #define MIN INT_MIN #define MAX INT_MAX #define LL long long using namespace std; int max(int a,int b){if(a>b)return a; else return b;} int min(int a,int b){if(a
        
         q; while(q.empty()==false) q.pop(); memset(num,0,sizeof(num)); memset(dis,-1,sizeof(dis)); q.push(sink); dis[sink]=0; num[0]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v = edge[i].v; if(dis[v] == -1) { dis[v] = dis[u] + 1; num[dis[v]]++; q.push(v); } } } } int ISAP(int source,int sink,int n) { memcpy(cur,head,sizeof(cur)); int flow=0, u = pre[source] = source; BFS( source,sink); while( dis[source] < n ) { if(u == sink) { int df = MAX, pos; for(int i = source;i != sink;i = edge[cur[i]].v) { if(df > edge[cur[i]].cap) { df = edge[cur[i]].cap; pos = i; } } for(int i = source;i != sink;i = edge[cur[i]].v) { edge[cur[i]].cap -= df; edge[cur[i]^1].cap += df; } flow += df; u = pos; } int st; for(st = cur[u];st != -1;st = edge[st].next) { if(dis[edge[st].v] + 1 == dis[u] && edge[st].cap) { break; } } if(st != -1) { cur[u] = st; pre[edge[st].v] = u; u = edge[st].v; } else { if( (--num[dis[u]])==0 ) break; int mind = n; for(int id = head[u];id != -1;id = edge[id].next) { if(mind > dis[edge[id].v] && edge[id].cap != 0) { cur[u] = id; mind = dis[edge[id].v]; } } dis[u] = mind+1; num[dis[u]]++; if(u!=source) u = pre[u]; } } return flow; } void initt() { memset(head,-1,sizeof(head)); bnum=0; } int main() { int np,nc,u,v,w; while(scanf(%d%d%d%d,&n,&np,&nc,&m) != EOF) { initt(); for(int i = 0;i
         
          
?