POJ 1459 Power Network
题目链接：http://poj.org/problem?id=1459
I/O坑爹。。
一开始的想法：
理论虽然简单，实现起来怀疑人生。
问题主要在于用什么模型存储网络，并且可以快速读写(这是核心问题)。
用矩阵存储一直TLE，后来一直想用map，但是感觉还是不行，最后还是换成链表了。
第一次写的，用矩阵存储。一直TLE，我以为矩阵费时间，，后来发现神tm居然控制台一直在等待输入，。。。
所以一直TLE！！！！要在scanf()前面加一个 ~(非)。。。
不过也挺好，写了两种实现，而且有些关键地方不一样：存储的是 点！！还是 边序号！！
不过用链表存图就是麻烦，经常pair，tuple满天飞。。。不知道有没有什么好的结构存储必要的连接信息。。
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;//POJ 1459 Power Networkconst int MAXN = 100 + 2;
const int inf = 0x7fffffff;
char temp[20]; //buffer
int main() {int n;while (~scanf("%d", &n)){int flow[MAXN][MAXN], cap[MAXN][MAXN];for (int i = 0; i < MAXN; ++i)for (int j = 0; j < MAXN; ++j){flow[i][j] = 0;cap[i][j] = 0;}int ps, c, l;scanf("%d %d %d", &ps, &c, &l);int S = n, T = n + 1;vector<vector<int> >node(n + 2); //node[i]数组 表示和i相连的点//读边for (int i = 0; i < l; ++i){int from, to, ca;scanf("%s", temp); sscanf(temp, "(%d,%d)%d", &from, &to, &ca);cap[from][to] = ca;if (cap[to][from])continue; //平行边重复记录node[from].push_back(to);node[to].push_back(from);}//读S相关的边for (int i = 0; i < ps; ++i){int to, ca;scanf("%s", temp); sscanf(temp, "(%d)%d", &to, &ca);cap[S][to] = ca;if (cap[to][S])continue; //平行边重复记录node[S].push_back(to);node[to].push_back(S);}//读T相关的边for (int i = 0; i < c; ++i){int from, ca;scanf("%s", temp); sscanf(temp, "(%d)%d", &from, &ca);cap[from][T] = ca;if (cap[T][from])continue; //平行边重复记录node[from].push_back(T);node[T].push_back(from);}int maxFlow = 0;vector<int> aug(n + 2); //aug[i] 表示S到i的可改进量vector<int> path(n + 2); //p[i] 表示增广路径上的 i的进入点//BFS查找增广路径while (true){for (int i = 0; i < n + 2; ++i)aug[i] = 0;queue<int>q;q.push(S);aug[S] = inf;while (!q.empty()){int x = q.front();q.pop();int size = node[x].size();for (int i = 0; i < size; ++i){int t = node[x][i];if (!aug[t] //访问过的就跳过，当然也可以不跳。。。&& (cap[x][t] > flow[x][t] //x->t|| flow[t][x] > 0) //t->x){path[t] = x; //记录进入点aug[t] = min(aug[x] //更新残存容量, max(cap[x][t] - flow[x][t], flow[t][x]));q.push(t);}}if (aug[T])break; //已经找到一条增广路径}if (!aug[T])break; //没有增广路径，结束，返回结果//有增广路径，从path[]倒着更新//这条路径上最小值就是aug[T]int min_aug = aug[T];for (int u = T; u != S; u = path[u]){if (flow[path[u]][u] < cap[path[u]][u])flow[path[u]][u] += min_aug;elseflow[u][path[u]] -= min_aug;}//流加上这个值maxFlow += min_aug;}//没有增广路径，结束，返回结果printf("%d\n", maxFlow);}system("pause");return 0;
}第二次写，用链表(数组实现)，
这个用时居然多一些，差点就想用tuple了，信息使用不如矩阵方便。。。
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;const int inf = 0x7fffffff;
char temp[20]; //bufferstruct Edge {int from, to, cap, flow;void set(int u, int v, int c, int f){from = u;to = v;cap = c;flow = f;}Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f) {}
};int main() {int n;while (~scanf("%d", &n)){int ps, c, l;scanf("%d %d %d", &ps, &c, &l);int S = n, T = n + 1;vector<vector<std::pair<int, bool> > > //node[i]数组 int表示和i相连的边序号node(n + 2); //bool表示 true 出边; false 入边vector<Edge> edges;int edge_num = 0; //边序号//读边for (int i = 0; i < l; ++i){int from, to, cap;scanf("%s", temp); sscanf(temp, "(%d,%d)%d", &from, &to, &cap);edges.push_back(Edge(from, to, cap, 0));node[from].push_back(make_pair(edge_num, 1));node[to].push_back(make_pair(edge_num, 0));edge_num++;}//读S相关的边for (int i = 0; i < ps; ++i){int to, cap;scanf("%s", temp); sscanf(temp, "(%d)%d", &to, &cap);edges.push_back(Edge(S, to, cap, 0));node[S].push_back(make_pair(edge_num, 1));node[to].push_back(make_pair(edge_num, 0));edge_num++;}//读T相关的边for (int i = 0; i < c; ++i){int from, cap;scanf("%s", temp); sscanf(temp, "(%d)%d", &from, &cap);edges.push_back(Edge(from, T, cap, 0));node[from].push_back(make_pair(edge_num, 1));node[T].push_back(make_pair(edge_num, 0));edge_num++;}int maxFlow = 0;vector<int> aug(n + 2); //aug[i] 表示S到i的可改进量vector<pair<int, bool> > path(n + 2); //p[i] 表示增广路径上的 i的进入边序号和方向//BFS查找增广路径while (true){for (int i = 0; i < n + 2; ++i)aug[i] = 0;queue<int> q;q.push(S);aug[S] = inf;while (!q.empty()){int x = q.front();q.pop();int size = node[x].size();for (int i = 0; i < size; ++i){//注：因为本题平行边的原因，//有可能会出现四次 x-tint num = node[x][i].first;bool out = node[x][i].second;Edge& e = edges[num];int t = out ? e.to : e.from;if (aug[t])continue; //访问过的就跳过，当然也可以不跳。。。if (out&&e.cap > e.flow) //x->t 还能进一些{path[t] = make_pair(num, 0); //记录进入边序号和方向aug[t] = min(aug[x], e.cap - e.flow); //更新残存容量q.push(t);}if (!out&&e.flow > 0) //x<-t 退回去一些{path[t] = make_pair(num, 1); //记录进入边序号和方向aug[t] = min(aug[x], e.flow); //更新残存容量q.push(t);}}if (aug[T])break; //已经找到一条增广路径}if (!aug[T])break; //没有增广路径，结束，返回结果//有增广路径，从path[]倒着更新//这条路径上最小值就是aug[T]int min_aug = aug[T];for (int u = T; u != S;){int num = path[u].first;bool out = path[u].second;if (!out) //原来的流：p_u-->uedges[num].flow += min_aug;else //原来的流：p_u<--uedges[num].flow -= min_aug;u = out ? edges[num].to : edges[num].from;}//流加上这个值maxFlow += min_aug;}//没有增广路径，结束，返回结果printf("%d\n", maxFlow);}system("pause");return 0;
}