想看更多的解题报告:http://blog.csdn.net/wangjian8006/article/details/7870410
转载请注明出处:http://blog.csdn.net/wangjian8006
题目大意:总共有n个节点,其中有发电站np个、用户nc个和调度器n-np-nc个三种节点,每个发电站有一个最大发电量,每个用户有个最大接受电量,现在有m条有向边,边有一个最大的流量代表,最多可以流出这么多电,现在从发电站发电到用户,问最多可以发多少电
解题思路:将发电站看成源点,用户看成汇点,这样求最大流就可以了,不过因为有多个源点和汇点,所以加一个超级源点指向所有的发电站,流量为无限大,加一个超级汇点让所有的用户指向他,流量也为无限大,这样,从超级源点到超级汇点求最大流即可。
题目比较简单,总结了几种最大流的算法
/* EdmondsKarp Memory 320K Time 1282MS 和没过没什么区别 */ #include <iostream> #include <queue> using namespace std; #define min(a,b) (a<b?a:b) #define MAXV 105 #define MAXINT INT_MAX typedef struct{ int flow; //流量 int capacity; //最大容量值 }maps; maps map[MAXV][MAXV]; int vertime; //顶点总数 int nedges; //边的总数 int power_stations; //发电站总数 int consumers; //消费者总数 int maxflow; //最大流 int sp,fp; //标记源点与汇点 int parent[MAXV]; //用于bfs寻找路径 int bfs(int start,int end){ int a[MAXV],i,v; queue <int>q; memset(a,0,sizeof(a)); memset(parent,-1,sizeof(parent)); q.push(start); a[start]=MAXINT; while(!q.empty()){ v=q.front();q.pop(); for(i=1;i<=vertime;i++){ if(!a[i] && map[v][i].capacity>map[v][i].flow){ q.push(i); parent[i]=v; a[i]=min(a[v],map[v][i].capacity-map[v][i].flow); } } if(v==end) break; } return a[end]; } void EdmondsKarp(){ int i,tmp; maxflow=0; while(tmp=bfs(sp,fp)){ for(i=fp;i!=sp;i=parent[i]){ map[i][parent[i]].flow-=tmp; //更新反向流 map[parent[i]][i].flow+=tmp; //更新正向流 } maxflow+=tmp; } } int main(){ int i; int x,y,z; char ch; while(scanf("%d%d%d%d", &vertime, &power_stations,&consumers,&nedges)!= EOF){ //Init memset(map,0,sizeof(map)); //Read Gragh for(i=1;i<=nedges;i++){ //设置读图从1开始 cin>>ch>>x>>ch>>y>>ch>>z; map[x+1][y+1].capacity=z; } //Build Gragh //建立超级源点指向所有的发电站 sp=vertime+1;fp=vertime+2;vertime+=2; for (i=1; i<=power_stations; i++){ cin>>ch>>x>>ch>>y; map[sp][x+1].capacity=y; } //建立超级汇点,使所有消费者指向它 for (i=1; i<=consumers; i++){ cin>>ch>>x>>ch>>y; map[x+1][fp].capacity=y; } EdmondsKarp(); printf("%d\n",maxflow); } return 0; }
===================================================================================================
/* dinic Memory 320K Time 563MS */ #include <iostream> #include <queue> using namespace std; #define min(a,b) (a<b?a:b) #define MAXV 105 #define MAXINT INT_MAX typedef struct{ int flow; //流量 int capacity; //最大容量值 }maps; maps map[MAXV][MAXV]; int dis[MAXV]; //用于dinic分层 int vertime; //顶点总数 int nedges; //边的总数 int power_stations; //发电站总数 int consumers; //消费者总数 int maxflow; //最大流 int sp,fp; //标记源点与汇点 bool bfs(){ int v,i; queue <int>q; memset(dis,0,sizeof(dis)); q.push(sp); dis[sp]=1; while(!q.empty()){ v=q.front();q.pop(); for(i=1;i<=vertime;i++) if(!dis[i] && map[v][i].capacity>map[v][i].flow){ q.push(i); dis[i]=dis[v]+1; } if(v==fp) return 1; } return 0; } int dfs(int cur,int cp){ if(cur==fp) return cp; int tmp=cp,t; for(int i=1;i<=vertime;i++) if(dis[i]==dis[cur]+1 && tmp && map[cur][i].capacity>map[cur][i].flow){ t=dfs(i,min(map[cur][i].capacity-map[cur][i].flow,tmp)); map[cur][i].flow+=t; map[i][cur].flow-=t; tmp-=t; } return cp-tmp; } void dinic(){ maxflow=0; while(bfs()) maxflow+=dfs(sp,MAXINT); } int main(){ int i; int x,y,z; char ch; while(scanf("%d%d%d%d", &vertime, &power_stations,&consumers,&nedges)!= EOF){ //Init memset(map,0,sizeof(map)); //Read Gragh for(i=1;i<=nedges;i++){ //设置读图从1开始 cin>>ch>>x>>ch>>y>>ch>>z; map[x+1][y+1].capacity=z; } //Build Gragh //建立超级源点指向所有的发电站 sp=vertime+1;fp=vertime+2;vertime+=2; for (i=1; i<=power_stations; i++){ cin>>ch>>x>>ch>>y; map[sp][x+1].capacity=y; } //建立超级汇点,使所有消费者指向它 for (i=1; i<=consumers; i++){ cin>>ch>>x>>ch>>y; map[x+1][fp].capacity=y; } dinic(); printf("%d\n",maxflow); } return 0; }
===========================================================================================
/* sap Memory 328K Time 454MS */ #include <iostream> #include <queue> using namespace std; #define MAXV 110 #define INF 1<<29 #define min(a,b) (a>b?b:a) int n,c[MAXV][MAXV],r[MAXV][MAXV],source,sink; int dis[MAXV],maxflow; void bfs(){ int v,i; queue <int>q; memset(dis,0,sizeof(dis)); q.push(sink); while(!q.empty()){ v=q.front();q.pop(); for(i=0;i<=sink;i++){ if(!dis[i] && c[i][v]>0){ dis[i] = dis[v] +1; q.push(i); } } } } void sap(){ int top=source,pre[MAXV],i,j,low[MAXV]; bfs(); //分层 memset(low,0,sizeof(low)); //保存路径的最小流量 while(dis[source]<n){ low[source]=INF; for(i=0;i<=sink;i++){ //找到一条允许弧 if(r[top][i]>0 && dis[top]==dis[i] +1) break; } if(i<=sink){ //找到了 low[i]=min(r[top][i],low[top]); //更新最小流量 pre[i]=top;top=i; //记录增广路径 if(top==sink){ //找到一条增广路径更新残量 maxflow += low[sink]; j = top; while(j != source){ i=pre[j]; r[i][j]-=low[sink]; r[j][i]+=low[sink]; j=i; } top=source; //再从头找一条增广路径 memset(low,0,sizeof(low)); } } else{ //找不到这样一条允许弧更新距离数组 int mindis=INF; for(j=0;j <=sink;j++){ if(r[top][j]>0 && mindis>dis[j] +1) mindis=dis[j] +1; } dis[top]=mindis; if(top!=source) top=pre[top]; } } } int main(){ int i,nedges,power_stations,consumers; int x,y,z; char ch; while(scanf("%d%d%d%d", &n, &power_stations,&consumers,&nedges)!= EOF){ //Init memset(r,0,sizeof(r)); memset(c,0,sizeof(c)); source=0;sink=n+1;n+=2;maxflow=0; //Read Gragh for(i=1;i<=nedges;i++){ //设置读图从1开始 cin>>ch>>x>>ch>>y>>ch>>z; c[x+1][y+1]=r[x+1][y+1]=z; } //Build Gragh //建立超级源点指向所有的发电站 for (i=1;i<=power_stations;i++){ cin>>ch>>x>>ch>>y; c[source][x+1]=r[source][x+1]=y; } //建立超级汇点,使所有消费者指向它 for (i=1;i<=consumers;i++){ cin>>ch>>x>>ch>>y; c[x+1][sink]=r[x+1][sink]=y; } sap(); printf("%d\n",maxflow); } return 0; }
=======================================================================================================
/* sap+分层+gap优化 Memory 328K Time 438MS */ #include <iostream> #include <queue> using namespace std; #define MAXV 110 #define INF 1<<29 #define min(a,b) (a>b?b:a) int n,c[MAXV][MAXV],r[MAXV][MAXV],source,sink; int dis[MAXV],maxflow,gap[MAXV]; void bfs(){ int v,i; queue <int>q; memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); gap[0]++; q.push(sink); while(!q.empty()){ v=q.front();q.pop(); for(i=0;i<=sink;i++){ if(!dis[i] && c[i][v]>0){ dis[i] = dis[v] +1; gap[dis[i]]++; q.push(i); } } } } void sap(){ int top=source,pre[MAXV],i,j,low[MAXV]; bfs(); //分层 memset(low,0,sizeof(low)); //保存路径的最小流量 while(dis[source]<n){ low[source]=INF; for(i=0;i<=sink;i++){ //找到一条允许弧 if(r[top][i]>0 && dis[top]==dis[i]+1 && dis[i]>=0) break; } if(i<=sink){ //找到了 low[i]=min(r[top][i],low[top]); //更新最小流量 pre[i]=top;top=i; //记录增广路径 if(top==sink){ //找到一条增广路径更新残量 maxflow += low[sink]; j = top; while(j != source){ i=pre[j]; r[i][j]-=low[sink]; r[j][i]+=low[sink]; j=i; } top=source; //再从头找一条增广路径 memset(low,0,sizeof(low)); } } else{ //找不到这样一条允许弧更新距离数组 int mindis=INF; for(j=0;j <=sink;j++){ if(r[top][j]>0 && mindis>dis[j] +1 && dis[j]>=0) mindis=dis[j] +1; } gap[dis[top]]--; if (gap[dis[top]] ==0) break; gap[mindis]++; dis[top]=mindis; if(top!=source) top=pre[top]; } } } int main(){ int i,nedges,power_stations,consumers; int x,y,z; char ch; while(scanf("%d%d%d%d", &n, &power_stations,&consumers,&nedges)!= EOF){ //Init memset(r,0,sizeof(r)); memset(c,0,sizeof(c)); source=0;sink=n+1;n+=2;maxflow=0; //Read Gragh for(i=1;i<=nedges;i++){ //设置读图从1开始 cin>>ch>>x>>ch>>y>>ch>>z; c[x+1][y+1]=r[x+1][y+1]=z; } //Build Gragh //建立超级源点指向所有的发电站 for (i=1;i<=power_stations;i++){ cin>>ch>>x>>ch>>y; c[source][x+1]=r[source][x+1]=y; } //建立超级汇点,使所有消费者指向它 for (i=1;i<=consumers;i++){ cin>>ch>>x>>ch>>y; c[x+1][sink]=r[x+1][sink]=y; } sap(); printf("%d\n",maxflow); } return 0; }