POJ - 1459 Power Network 最大流模版，有点意思的输入-白红宇

POJ - 1459 Power Network 最大流模版，有点意思的输入

阅读量：497 次

发布时间：2019-03-07

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

题目大意是说，有n个节点，其中包含发电站、中转站和用电器，m条路线，每条路线有流量限制。目标是求最大用电器功率。

思路：

将题目建模为最大流问题，构造一个图，其中：

源点s连接发电站，边权重为发电量。

发电站连接到中转站，边权重无穷大。

中转站连接到用电器，边权重为用电器功率。

用电器连接到汇点t，边权重为0。

使用Dinic算法计算s到t的最大流，最大流即为最大用电器功率。

代码：

#include 
   
    #include 
    #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define endl "\n"#define int long longconst int inf=0x3f3f3f3f;const int maxn=1010;const int maxe=50010;int head[maxn], cnt;struct Edge { int v, w, next;};ll maxflow = 0;int deep[maxn];int now[maxe];void init() { memset(head, -1, sizeof(head)); cnt = 0; maxflow = 0;}void add(int u, int v, int w) { edge[cnt].v = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++;}inline bool bfs() { memset(deep, -1, sizeof(deep)); queue
            
              q; q.push(s); deep[s] = 0; now[s] = head[s]; while (!q.empty()) { int x = q.front(); q.pop(); for (int i = head[x]; i != -1; i = edge[i].next) { int y = edge[i].v; if (edge[i].w > 0 && deep[y] == -1) { deep[y] = deep[x] + 1; now[y] = i; q.push(y); if (y == t) return true; } } } return false;}ll dfs(int x, ll flow) { if (x == t) return flow; ll ans = 0; for (int i = now[x]; i != -1; i = edge[i].next) { int y = edge[i].v; if (edge[i].w > 0 && deep[y] == deep[x] + 1) { ll min_flow = min(flow, edge[i].w); ll ret = dfs(y, min_flow); if (ret > 0) { ans += ret; edge[i].w -= ret; edge[i^1].w += ret; } } } return ans;}void dinic() { while (bfs()) { maxflow += dfs(s, INF); }}int main() { while (true) { vector
             
               res; string s, t; istringstream iss; int n, n1, n2, m; while (true) { iss >> s, t; if (s.find('(') == string::npos) break; } istringstream iss2; while (iss2 >> n >> n1 >> n2 >> m) { init(); int s_node, t_node; s_node = n + 5; t_node = s_node + 1; for (int i = 0; i < m; i++) { int u, v, w; iss >> u >> v >> w; add(u, v, w); add(v, u, 0); } for (int i = 0; i < n1; i++) { int u, w; iss >> u >> w; add(s_node, u, w); add(u, s_node, 0); } for (int i = 0; i < n2; i++) { int u, w; iss >> u >> w; add(u, t_node, w); add(t_node, u, 0); } dinic(); cout << maxflow << endl; } return 0; }}