HDU-3549Flow Problem 最大流模板题_学习

HDU-3549Flow Problem 最大流模板题

admin

2024-01-29 21:58:35

传送门

这里是Ford-Fulkerson写的最大流模板

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue#define Pll pair
#define Pii pair#define fi first
#define se second#define OKC ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;/*-----------------show time----------------*/
const int maxn = 1e3+9;
struct node {int to,cap,rev;
};vectormp[maxn];
bool used[maxn];void add_edge(int from,int to,int cap)
{mp[from].pb((node){to,cap,(int)mp[to].size()});mp[to].pb((node){from,0,(int)mp[from].size()-1});   
}int dfs(int v,int t,int f)
{if(v==t)return f;used[v] = true;for(int i=0; i0){int d = dfs(e.to,t,min(f,e.cap));if(d>0){e.cap -= d;mp[e.to][e.rev].cap += d;return d;}}}return 0;
}int max_flow(int s,int t)
{int flow = 0;for(;;){memset(used,0,sizeof(used));int f = dfs(s,t,inf);if(f==0)return flow;flow += f;}
}
int main(){int t,n,m;scanf("%d", &t);for(int T=1; T<=t;T++){scanf("%d%d", &n, &m);for(int i=0;i<=n;i++)mp[i].clear();for(int i=1; i<=m; i++){int u,v,c;scanf("%d%d%d", &u, &v, &c);add_edge(u,v,c);}printf("Case %d: %d\n",T,max_flow(1,n));}return 0;
}

HDU 3549

上一篇：有哪些说米托秀秀厉害的句子？

下一篇：北堡山下的一泊哲学句子

HDU-3549Flow Problem 最大流模板题

相关内容

热门资讯