HDU 3549 Flow Problem（最大流）
Time Limit: 5000/5000 MS (Java/Others)
Memory Limit: 65536/32768 K (Java/Others)
|
【Description】 |
【题目描述】 |
|
Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph. |
网络流是ACMers众所周知的一个难题。给定一幅图，你的任务是找出这个加权有向图的最大流。 |
|
【Input】 |
【输入】 |
|
The first line of input contains an integer T, denoting the number of test cases. For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000) Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000) |
输入的第一行是一个整数T，表示测试用例的数量。 对于每个测试用例，第一行有两个整数N和M，表示图中顶点与边的数量。（2 <= N <= 15, 0 <= M <= 1000）接着M行，每行三个整数X,Y和C，有一条从X到Y的边，其容量为C。(1 <= X, Y <= N, 1 <= C <= 1000) |
|
【Output】 |
【输出】 |
|
For each test cases, you should output the maximum flow from source 1 to sink N. |
对于每个测试样例，输出从源点1到汇点N的最大流。 |
|
【Sample Input - 输入样例】 |
【Sample Output - 输出样例】 |
|
2 3 2 1 2 1 2 3 1 3 3 1 2 1 2 3 1 1 3 1 |
Case 1: 1 Case 2: 2 |
【题解】
最大流问题
题目描述得太简单，自己从来没做过，就去百度了一下大概的规则
然后……就当成水管来看吧…………
比较简单的方式的用DFS实现，注意处理好搜索与回溯即可。
搜索时可以每次只找一条1→N的路径，也可以在当前已走过的路径下尽可能地推送流量到N，即多条路径（不过这种方式比较费时，因为会在重复尝试一些无效的路径）
为了方便回溯，每次A→B推送的流量等于添加B→A的容量。
vector的查询速度并不是很快，多次使用的时候用指针或是继承可以提高速度，以及看/写起来舒服点……
【代码 C++】
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
int n;
struct edge{
int next, capacity, last_i;
};
std::vector<edge> data[];
bool us[];
void read(){
int m, x, y, c, i, j, map[][];
memset(map, , sizeof(map));
scanf("%d%d", &n, &m);
for (i = ; i <= n; ++i) data[i].clear();
for (i = ; i < m; ++i) scanf("%d%d%d", &x, &y, &c), map[x][y] += c;
edge temp = { , , };
for (i = ; i < n; ++i){
for (j = i + ; j <= n; ++j){
if (map[i][j] + map[j][i] == ) continue;
temp.next = j; temp.capacity = map[i][j]; temp.last_i = data[j].size();
data[i].push_back(temp);
temp.next = i; temp.capacity = map[j][i]; temp.last_i = data[i].size() - ;
data[j].push_back(temp);
}
}
}
int send(int nowEdge, int flowWait){
if (nowEdge == n) return flowWait;
us[nowEdge] = ;
int hadSend, temp, i, ed = data[nowEdge].size();
for (i = hadSend = ; i < ed; ++i){
edge &now = data[nowEdge][i];
if (!us[now.next] && now.capacity){
temp = send(now.next, std::min(now.capacity, flowWait - hadSend));
if (temp){
hadSend += temp; now.capacity -= temp;
data[now.next][now.last_i].capacity += temp;
}
}
}
return hadSend;
}
int main(){
int t, i, opt, temp;
for (i = scanf("%d", &t); i <= t; ++i){
printf("Case %d: ", i);
read();
for (opt = ; memset(us, , sizeof(us));){
temp = send(, );
if (temp) opt += temp;
else break;
}
printf("%d\n", opt);
}
return ;
}