【最大流 模板 Dinic】POJ 1459 Power Network

2019-04-14 08:42发布

站内文章 / 模拟电子
12767 0 1666
Problem Description
给你n, np, nc, m。分别代表有n个点，其中np个是发电站，nc个是消费者，剩下n-np-nc个就是中转站。接下来给你m条边，每条边格式(u,v)w。代表u点到v点这条线路最大能够运输w的电。最后给你np个点最大能够输出的电，nc个点最大能够接收的电（格式：(u)w, u这个点能够输出（接收）最大的电，发电站的点是输出，消费者的点是接收）。
思路：
所有发电站看成一个超级源点s，所有消费者看成一个超级汇点t。如何实现，从s向每个源点连一条容量为对应最大流出容量的边，从每个汇点向t连一条容量为对应最大流入容量的边。然后求s->t的最大流即可。
给了两种形式的Dinic。存图都用了邻接矩阵，这样可以好观察出两种Dinic的那些细节不一样 时间复杂度O(|E||V|^2) #include #include #include #include using namespace std; const int mm = 200; const int inf = 0x3f3f3f3f; int Map[mm][mm], n;//存图 int dis[mm];//记录mm到超级源点的最短距离 void bfs(int s, int t)//求dis[]数组 { memset(dis, -1, sizeof(dis)); dis[s] = 0; queue<int> q; q.push(s); while(!q.empty()) { s = q.front(); q.pop(); for(int i = 1; i <= t; i++) { if(dis[i] == -1 && Map[s][i])//容量不为0 { dis[i] = dis[s] + 1; q.push(i); } } } } int dfs(int s, int t, int f)//s为当前点，t为超级汇点，f为当前流入s点的流量 { if(s == t) return f;//代表到达超级汇点，直接返回当前流到汇点的流量 int ans = 0;//用来记录当前点，输出的最大流量 for(int i = 1; i <= t; i++) { if(Map[s][i] && dis[i] > dis[s]) { int d = dfs(i, t, min(f, Map[s][i])); if(d > 0)//代表到达了汇点，到达汇点的这条增广路，最小的流量(限制流量) { Map[s][i] -= d;//正向边-d Map[i][s] += d;//反向边+d ans += d;//更新当前点的，输出的最大流量 f -= d;//到达当前点的流量-d if(!f) break;//如果当前点已经没有可以输出的流量，退出循环 } } } if(ans) return ans;//当前点，输出的最大流量有的话 dis[s] = -1;//没有就标记-1，再到这点也没意义了。 return 0; } int Dinic(int s, int t) { int Max_flow = 0, flow; for(;;){ bfs(s, t);//先跑bfs if(dis[t] < 0) break;//代表到达不了t，直接退出循环 Max_flow += dfs(s, t, inf);//更新最大流 } return Max_flow; } int main() { int np, nc, m, u, v, w, i; char s[20]; while(~scanf("%d %d %d %d", &n, &np, &nc, &m)) { memset(Map, 0, sizeof(Map));//初始化 while(m--)//建图 { scanf("%s", s); sscanf(s, "%*c%d%*c%d%*c%d", &u, &v, &w); Map[u + 1][v + 1] = w; } for(i = 0; i < np; i++) { scanf("%s", s); sscanf(s, "%*c%d%*c%d", &u, &w); Map[0][u + 1] = w; } n = n + 1; for(i = 0; i < nc; i++) { scanf("%s", s); sscanf(s, "%*c%d%*c%d", &u, &w); Map[u + 1][n] = w; } //0为超级源点，n为超级汇点 printf("%d ", Dinic(0, n)); } return 0; } 第二种类型主要就标识一下，那些地方不一样。就不那么详细的注释了 #include #include #include #include using namespace std; const int mm = 200; const int inf = 0x3f3f3f3f; int Map[mm][mm], n; int dis[mm], iter[mm];//多了个iter[]数组,作用当前弧，在其之前的边已经没有用了。 void bfs(int s, int t) { memset(dis, -1, sizeof(dis)); dis[s] = 0; queue<int> q; q.push(s); while(!q.empty()) { s = q.front(); q.pop(); for(int i = 1; i <= t; i++) { if(dis[i] == -1 && Map[s][i]) { dis[i] = dis[s] + 1; q.push(i); } } } } int dfs(int s, int t, int f) { if(s == t) return f; for(int &i = iter[s]; i <= t; i++)//i是取iter[s]地址 //下一次dfs的时候就可以直接跳过之前s为起点，访问过的边，这就是iter[]的作用，避免浪费的搜索 { if(i == 0) continue;//从1点开始搜索 if(Map[s][i] && dis[i] > dis[s]) { //这里是直接找到增光路，然后一路返回到超级源点，然后退出循环，这时候你就能理解调用的时候为什么是循环，iter[]数组为何要这样了。 int d = dfs(i, t, min(f, Map[s][i])); if(d > 0) { Map[s][i] -= d; Map[i][s] += d; return d; } } } return 0; } int Dinic(int s, int t) { int Max_flow = 0, flow; for(;;){ bfs(s, t); if(dis[t] < 0) break; memset(iter, 0, sizeof(iter));//初始化为0，但是是从1点开始搜，所以一会儿加个continue就可以了 while((flow = dfs(s, t, inf)) > 0)//不一样的点。这里是循环，一会儿解释为什么 { Max_flow += flow; } } return Max_flow; } int main() { int np, nc, m, u, v, w, i; char s[20]; while(~scanf("%d %d %d %d", &n, &np, &nc, &m)) { memset(Map, 0, sizeof(Map)); while(m--) { scanf("%s", s); sscanf(s, "%*c%d%*c%d%*c%d", &u, &v, &w); Map[u + 1][v + 1] = w; } for(i = 0; i < np; i++) { scanf("%s", s); sscanf(s, "%*c%d%*c%d", &u, &w); Map[0][u + 1] = w; } n = n + 1; for(i = 0; i < nc; i++) { scanf("%s", s); sscanf(s, "%*c%d%*c%d", &u, &w); Map[u + 1][n] = w; } printf("%d ", Dinic(0, n)); } return 0; }

热门文章