题目类型 多源多汇最大流
题目意思
给出 ns 个供电点最大提供的电量 和 nt 个用电点最大的用电量 以及中间一些运输线的最大容纳的电量
问最多有多少电量从供电点运输到用电点
解题方法
构造一个超级源点s和一个超级汇点t 然后s到供电点的边的容量就是供电点最大提供的电量 用电点到t的边的容量就是用电点最大的用电量 然后对于一条输电线(u,v,w) 即u点到v点的边的容量为w
建好图后跑一次s->t最大流即为所求
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
ISAP:
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <stack> #include <cmath> #include <vector> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 1000 + 10; const int INF = 1<<30; struct Edge { int from, to, cap, flow; Edge(int a, int b, int c, int d) : from(a), to(b), cap(c), flow(d) {} }; int tn; struct ISAP { int p[maxn], num[maxn], d[maxn], cur[maxn]; int n, s, t, flow; // n 个点 vector<Edge>edges; vector<int>G[maxn]; void AddEdge(int from, int to, int cap) { //加边 //if(from == 0 && to == 3) printf("ff %d -- > %d %d\n", from, to, cap); edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); int m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } int Augment() { //增广 int x = t, a = INF; while(x != s) { Edge & e = edges[p[x]]; a = min(a, e.cap - e.flow); x = edges[p[x]].from; } x = t; while(x != s) { edges[p[x]].flow += a; edges[p[x]^1].flow -= a; x = edges[p[x]].from; } return a; } void BFS() { //预处理 距离t 的距离 for( int i=0; i<n; i++ ) d[i] = n; queue<int>Q; Q.push(t); d[t] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for( int i=0; i<G[x].size(); i++ ) { Edge & e = edges[G[x][i]^1]; if(d[e.from] == n && e.cap > e.flow) { d[e.from] = d[x] + 1; Q.push(e.from); } } } } int Maxflow(int s, int t) { //求最大流 int flow = 0; this->s = s, this->t = t; memset(num, 0, sizeof(num)); memset(cur, 0, sizeof(cur)); BFS(); for( int i=0; i<n; i++ ) num[d[i]]++; int x = s; while(d[s] < n) { if(x == t) { flow += Augment(); x = s; } int ok = 0; for( int i=cur[x]; i<G[x].size(); i++ ) { Edge & e = edges[G[x][i]]; if(e.cap > e.flow && d[x] == d[e.to] + 1) { ok = 1; p[e.to] = G[x][i]; cur[x] = i; x = e.to; break; } } if(!ok) { int m = n-1; for( int i=0; i<G[x].size(); i++ ) { Edge & e = edges[G[x][i]]; if(e.cap > e.flow) m = min(m, d[e.to]); } if(--num[d[x]] == 0) break; num[d[x] = m+1]++; cur[x] = 0; if(x != s) x = edges[p[x]].from; } } return flow; } void Init(int n) { //初始化 this->n = n; edges.clear(); for( int i=0; i<=n; i++ ) G[i].clear(); } vector<int> Mincut() { BFS(); vector<int>cut; for( int i=0; i<edges.size(); i++ ) { Edge e = edges[i]; if(d[e.from] == n && d[e.to] != n) { cut.push_back(i); } } return cut; } }p; int A[maxn][maxn], win[maxn], can[maxn]; int main() { freopen("in", "r", stdin); int n; while(scanf("%d", &n) != EOF) { p.Init(n+2); int ns, nt, m; scanf("%d%d%d", &ns, &nt, &m); for( int i=0; i<m; i++ ) { int u, v, w; char str[100]; scanf("%s", str); sscanf(str, "(%d,%d)%d", &u, &v, &w); p.AddEdge(u, v, w); //printf("%d %d %d\n", u, v, w); } for( int i=0; i<ns; i++ ) { char str[100]; int u, c; scanf("%s", str); sscanf(str, "(%d)%d", &u, &c); p.AddEdge(n, u, c); //printf("%d %d\n", u, c); } for( int i=0; i<nt; i++ ) { char str[100]; int u, c; scanf("%s", str); sscanf(str, "(%d)%d", &u, &c); p.AddEdge(u, n+1, c); //printf("%d %d\n", u, c); } printf("%d\n", p.Maxflow(n, n+1)); } return 0; }