首页 > 代码库 > HDU 1532

HDU 1532

2024-09-12 19:00:14   217人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1532

题意： 

三叶草是这个人的最喜欢的植物，结果下雨淹没了他家里，要排水，一个点到一个点的排水速度已知，求最大排水能力。

 

我仔细看了题面，好像是没有具体说明起点和终点。

所以我用最大流，枚举起点终点，并且清流，当然我知道还是可能超时的。

看了一下网上的解答，硬说起点是 1 ，终点 m，我也是很迷啊~~~

技术分享
  1 #include <bits/stdc++.h>  2   3 using namespace std;  4   5 const int maxn = 205;  6 const int INF = 0x3f3f3f3f;  7   8 struct Edge {  9     int from,to,cap,flow; 10 }; 11  12 struct Dinic { 13  14     int n,m,s,t; 15     vector<Edge> edges; 16     vector<int> G[maxn]; 17     bool vis[maxn]; 18     int d[maxn]; 19     int cur[maxn]; 20  21     void init(int n) { 22         this->n = n; 23         for(int i=0;i<n;i++) 24             G[i].clear(); 25         edges.clear(); 26     } 27  28     void clearflow() { 29         for(int i=0;i<edges.size();i++) 30             edges[i].flow = 0; 31     } 32  33  34     void AddEdge(int from,int to,int cap) { 35         edges.push_back((Edge){from,to,cap,0}); 36         edges.push_back((Edge){to,from,0,0}); 37         m = edges.size(); 38         G[from].push_back(m-2); 39         G[to].push_back(m-1); 40     } 41  42     bool BFS() { 43         memset(vis,0,sizeof(vis)); 44         queue<int> Q; 45         Q.push(s); 46         vis[s] = 1; 47         while(!Q.empty()) { 48             int x = Q.front();Q.pop(); 49             for(int i=0;i<G[x].size();i++) { 50                 Edge& e = edges[G[x][i]]; 51                 if(!vis[e.to]&&e.cap>e.flow) { 52                     vis[e.to] = 1; 53                     d[e.to] = d[x] + 1; 54                     Q.push(e.to); 55                 } 56             } 57         } 58         return vis[t]; 59     } 60  61  62     int DFS(int x,int a) { 63         if(x==t||a==0) return a; 64         int flow = 0,f; 65         for(int& i=cur[x];i<G[x].size();i++) { 66             Edge& e = edges[G[x][i]]; 67             if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { 68                 e.flow +=f; 69                 edges[G[x][i]^1].flow -=f; 70                 flow+=f; 71                 a-=f; 72                 if(a==0) break; 73             } 74         } 75         return flow; 76     } 77  78     int Maxflow(int s,int t) { 79         this->s = s;this->t = t; 80         int flow = 0; 81         while(BFS()) { 82             memset(cur,0,sizeof(cur)); 83             flow+=DFS(s,INF); 84         } 85         return flow; 86     } 87  88  89 }sol; 90  91 int main() 92 { 93     int n,m; 94     while(~scanf("%d%d",&n,&m)) { 95         sol.init(n); 96         for(int i=0;i<n;i++) { 97             int u,v,c; 98             scanf("%d%d%d",&u,&v,&c); 99             u--;100             v--;101             sol.AddEdge(u,v,c);102         }103 104        // int ans = -1;105        // for(int s=0;s<m;s++) {106        //     for(int t=s+1;t<m;t++) {107        //         sol.clearflow();108        //         ans = max(ans,sol.Maxflow(s,t));109        //     }110        // }111 112        // int ans = sol.Maxflow(0,m-1);113 114       // int s = m,t=m+1;115        //for(int i=0;i<m;i++) {116        //     sol.AddEdge(s,i,INF);117       //      sol.AddEdge(i,t,INF);118        //}119 120        printf("%d\n",sol.Maxflow(0,m-1));121 122        // printf("%d\n",ans);123 124     }125     return 0;126 }
View Code

 

HDU 1532


联系
我们