Light OJ 1153

题目链接

---

题意：
给定源点Source和汇点Destination，每条网络的最大带宽，求在网络中传送数据的最大带宽。

题面就是最大流。

使用最简单的最常用的模板Dinic

使用BFS分层残量网络，找到增广路，再使用DFS进行增广。

---

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <math.h>
#include <bitset>
#include <ctype.h>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-9;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int t, kase = 0;
int n, S, T, m;

struct Edge
{
	int u, v, flow, cap;
	Edge(){}
	Edge(int a, int b, int c, int d):u(a), v(b), cap(c), flow(d){}
};
struct Dinic
{
	int n;
	vector<int> G[N];
	vector<Edge> edges;
	int cur[N], vis[N], d[N];
	void init(int n)
	{
		this->n = n;
		for(int i = 0; i <= n; i++) G[i].clear();
		edges.clear();
	}
	void addEdge(int u, int v, int cap)
	{
		edges.push_back(Edge(u, v, cap, 0));
		edges.push_back(Edge(v, u,   0, 0));
		int m = edges.size();
		G[u].push_back(m-2);
		G[v].push_back(m-1);
	}

	bool BFS(int s, int t)
	{
		queue<int> Q;
		Q.push(s);
		memset(vis, 0, sizeof(vis));
		d[s] = 0;
		vis[s] = 1;
		while(!Q.empty())
		{
			int u = Q.front(); Q.pop();
			for(int i = 0; i < (int)G[u].size(); i++)
			{
				Edge &e = edges[G[u][i]];
				int v = e.v;
				if(vis[v]) continue;
				if(e.cap > e.flow)
				{
					vis[v] = 1;
					d[v] = d[u] + 1;
					Q.push(v);
				}
			}
		}
		return vis[t];
	}

	int DFS(int x, int a, int t)
	{
		if(x == t || a == 0) return a;
		int f, flow = 0;
		for(int &i = cur[x]; i < G[x].size(); i++)
		{
			Edge &e = edges[G[x][i]];
			int v = e.v;
			if(d[v] == d[x] + 1 && (f = DFS(v, min(e.cap-e.flow, a), t)) > 0)
			{
				e.flow += f;
				edges[G[x][i]^1].flow -= f;
				flow += f;
				a -= f;
				if(a <= 0) break;
			}
		}
		return flow;
	}

	int MaxFlow(int s, int t)
	{
		int flow = 0;
		while(BFS(s, t))
		{
			memset(cur, 0, sizeof(cur));
			flow += DFS(s, INF, t);
		}
		return flow;
	}

}dinic;

int main()
{
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		dinic.init(n);
		scanf("%d%d%d", &S, &T, &m);
		for(int i = 0; i < m; i++)
		{
			int u, v, c;
			scanf("%d%d%d", &u, &v, &c);
			dinic.addEdge(u, v, c);
			dinic.addEdge(v, u, c);
		}
		printf("Case %d: %d
", ++kase, dinic.MaxFlow(S, T));
	}
	return 0;
}