首页 > 代码库 > hdoj 3549 Flow Problem 【最大流】
hdoj 3549 Flow Problem 【最大流】
题目:hdoj 3549 Flow Problem
题意:给出一个图,让你求最大流。
分析:这个题目用dinci写的,因为点比较少,而dinci复杂度O(m*n^2),但是还是跑了160ms,不知道15的神牛怎么写的。
dinci的写法要注意的地方就是存图的时候要考虑怎么存,因为要更新网络残量,即反向的流量,所以这里要注意一下。
思想就不讲了,很多地方有讲。
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> using namespace std; #define Del(a,b) memset(a,b,sizeof(a)) const int N = 20; const int inf = 0x3f3f3f3f; int n,m; struct Node { int from,to,cap,flow; }; vector<int> v[N]; vector<Node> e; int vis[N]; // void add_Node(int from,int to,int cap) { e.push_back((Node){from,to,cap,0}); e.push_back((Node){to,from,0,0}); int tmp=e.size(); v[from].push_back(tmp-2); v[to].push_back(tmp-1); } bool bfs(int s,int t) { Del(vis,-1); queue<int> q; q.push(s); vis[s] = 0; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i<v[x].size();i++) { Node tmp = e[v[x][i]]; if(vis[tmp.to]<0 && tmp.cap>tmp.flow) //第二个条件保证 { vis[tmp.to]=vis[x]+1; q.push(tmp.to); } } } if(vis[t]>0) return true; return false; } int dfs(int o,int f,int t) { if(o==t || f==0) return f; int a = 0,ans=0; for(int i=0;i<v[o].size();i++) { Node &tmp = e[v[o][i]]; if(vis[tmp.to]==(vis[o]+1) && (a = dfs(tmp.to,min(f,tmp.cap-tmp.flow),t))>0) { tmp.flow+=a; e[v[o][i]^1].flow-=a; //存图方式 ans+=a; f-=a; } } return ans; //优化 } int dinci(int s,int t) { int ans=0; while(bfs(s,t)) { int tm=dfs(s,inf,t); //printf("%d\n",tm); ans+=tm; } return ans; } int main() { //freopen("Input.txt","r",stdin); int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int x,y,c; scanf("%d%d%d",&x,&y,&c); add_Node(x,y,c); } printf("Case %d: %d\n",cas,dinci(1,n)); for(int i=1;i<=n;i++) v[i].clear(); e.clear(); } return 0; }
hdoj 3549 Flow Problem 【最大流】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。