首页 > 代码库 > HDU 3549 Flow Problem ( 最大流 -EK 算法)
HDU 3549 Flow Problem ( 最大流 -EK 算法)
C++,G++的读取速度差距也太大了
Flow Problem
题意:n,m表示n个点m条有向带权边
问:从1-n最大流多少
裸最大流,拿来练手,挺不错的
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> const int N = 210; #define MIN INT_MIN #define MAX INT_MAX #define LL long long using namespace std; int max(int a,int b){if(a>b)return a; else return b;} int min(int a,int b){if(a<b)return a; else return b;} int c[100][100]; int re[100]; int f[100][100]; int p[100],n,m; void init() { for(int i = 0;i<=n;i++) { for(int j = 0;j<=n;j++) { c[i][j] = f[i][j] = 0; } p[i] = 0; } } void EK(int s,int t) { queue<int >q; while(q.empty()==false) q.pop(); int sum = 0; while(1) { memset(re,0,sizeof(re)); q.push(s); re[s] = MAX; p[s] = -1; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = 1;i<=n;i++) { if(!re[i] && f[u][i] < c[u][i]) { q.push(i); p[i] = u; re[i] = min(re[u],c[u][i]-f[u][i]); } } } if(re[t]==0) break; for(int st = t;st!=s;st = p[st]) { f[p[st]][st] += re[t]; f[st][p[st]] -= re[t]; } sum += re[t]; } printf("%d\n",sum); } int main() { int t,C=0,a,b,w; scanf("%d",&t); while(t--) { C++; scanf("%d%d",&n,&m); init(); for(int i = 0;i<m;i++) { scanf("%d%d%d",&a,&b,&w); c[a][b] += w; } printf("Case %d: ",C); EK(1,n); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。