题意： 简单的说下题意（按输入输出来讲，前面的描述一堆的rubbish，还用来误导人），给你n个点，其中有np个是能提供电力的点，nc个是能消费电力的点，剩下的点(n-np-nc)是中转战即不提供电力也不消费电力，点与点之间是有线路存在的，有m条线路，每条线路有最多运载限定。 前4个数据就是有n个点，np个供电点,nc个消费点,m条线路，接来题目先给出的是m条线路的数据，(起点,终点)最多运载量,然后是np个供电点的数据(供电点)最多供电量，接着就是nc个消费点的数据(消费点)最多消费电量。 题目要我们求出给定的图最大能消费的总电量（就是求最大流）
思路： 供电点有提供功能，那么供电点就可以当成源点，同样消费点有消费功能，可以当成汇点。 由于这题有多个供电点和消费点，我们可以增加两个点，一个超级源点和一个超级汇点。 把所有的供电点都当成是由超级源点提供电量的，所有的消费点都将消费电量转移到超级汇点上，这样就相当于转换成一个基本的网络流求最大流的题。 超级源点与供电点有一条边，边的值为供电点最大能提供的电量，消费点与超级汇点有一条边，边的值为消费点最大能消费的电量。
就是采用基本的网络流求最大流算法中的Edmonds-Karp 如果想用scanf来加速可以这样写 主要是题目输入坑，每个括号前可以有任意多个空格，对cin没影响但是对scanf有影响 scanf(“%*^(%d”, &first, &next, &value); scanf(“%*^(%d”, &first, &value);
#include<iostream> #include<algorithm> #include<fstream> #include<math.h> #include<algorithm> #include<stack> #include<queue> using namespace std; fstream fin("1.txt"); //streambuf *buf = cin.rdbuf(fin.rdbuf());//用于重定项输入改成，把cin当成fin const int inf = 1 << 29; const int MAXN = 310; int n, np, nc, m; int map[MAXN][MAXN]; bool vis[MAXN]; int pre[MAXN]; void init()//初始化 { int len = n + 2; for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { map[i][j] = 0; } } } int getmin(int a, int b) { return a < b ? a : b; } int getroute(int s, int e)//bfs求源点到汇点的路径 { int len = n + 2; int temp; for (int i = 0; i < len; i++) { vis[i] = false; pre[i] = -1; } bool haveroute = false; queue<int> que; que.push(s); vis[s] = true; while (!haveroute && !que.empty()) { temp = que.front(); que.pop(); for (int i = 0; i < len; i++) { if (map[temp][i] && !vis[i]) { vis[i] = true; pre[i] = temp; if (i == e) { haveroute = true; break; } que.push(i); } } } if (!haveroute) return false; return true; } int getMaxflow(int s, int e)//求最大流 { int t; int result = 0; while (getroute(s, e)) { int minflow = inf; t = e; while (pre[t] != -1)//寻找路线中最小的线路 { minflow = getmin(minflow, map[pre[t]][t]); t = pre[t]; } t = e; while (pre[t] != -1)//增广路 { map[pre[t]][t] -= minflow; map[t][pre[t]] += minflow; t = pre[t]; } result += minflow; } return result; } int main() { char rubbish; int first, next; int value; while (cin >> n >> np >> nc >> m) { init(); int start = n; int end = n + 1; for (int i = 0; i < m; i++) { cin >> rubbish; cin >> first; cin >> rubbish; cin >> next; cin >> rubbish; cin >> value; if (first == next) continue; map[first][next] = value; } for (int i = 0; i < np; i++) { cin >> rubbish; cin >> first; cin >> rubbish; cin >> value; map[start][first] = value;//超级源点与供电点相连 } for (int i = 0; i < nc; i++) { cin >> rubbish; cin >> first; cin >> rubbish; cin >> value; map[first][end] = value;//超级汇点与消费点相连 } cout << getMaxflow(start, end) << endl; } return 0; } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136