ACM/ICPC 之电力网络-EK算法(POJ1459)-白红宇

ACM/ICPC 之电力网络-EK算法(POJ1459)

阅读量：5065 次

发布时间：2019-06-12

本文共 1360 字，大约阅读时间需要 4 分钟。

　　按照电站发电（从源点到电站），消费者消费（从消费者到汇点）的想法构建网络，以下是EK解法

//网络流EK算法//Time:922Ms    memory:224K#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAX 105#define INF 0x3f3f3f3fint n,np,nc,m;int s,t;int res[MAX][MAX];  //残留网络int pre[MAX];bool bfs(){    memset(pre,-1,sizeof(pre));    queue
          
            q; q.push(s); pre[s] = 0; while(!q.empty()){ int cur = q.front(); q.pop(); for(int i = 1; i <= t; i++) { if(pre[i] == -1 && res[cur][i]) { pre[i] = cur; if(i == t) return true; q.push(i); } } } return false;}int EK(){ int maxFlow = 0; while(bfs()){ int alpha = INF; //最小可改进量 for(int i = t; i != s; i = pre[i]) alpha = min(alpha, res[pre[i]][i]); for(int i = t; i != s; i = pre[i]) { res[pre[i]][i] -= alpha; res[i][pre[i]] += alpha; } maxFlow += alpha; } return maxFlow;}int main(){ //freopen("in.txt", "r", stdin); while(~scanf("%d%d%d%d", &n,&np,&nc,&m)){ s = 0; t = n+2; memset(res,0,sizeof(res)); int a,b,c; while(m--){ scanf(" (%d,%d)%d", &a,&b,&c); res[a+1][b+1] = c; } for(int i = 0; i < np; i++) { //电站 scanf(" (%d)%d", &b,&c); res[s][b+1] = c; } for(int i = 0; i < nc; i++) { //消费 scanf(" (%d)%d", &a,&c); res[a+1][t] = c; } printf("%d\n", EK()); } return 0;}