HDU 3549 Flow Problem
4788 단어 HDU
Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem 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.
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)
Output
For each test cases, you should output the maximum flow from source 1 to sink N.
Sample Input
2 3 2 1 2 1 2 3 1 3 3 1 2 1 2 3 1 1 3 1
Sample Output
Case 1: 1 Case 2: 2
제목:
사실은 우리 에 게 가장 큰 흐름 의 템 플 릿 문 제 를 구 하 라 는 것 이다.
첫 번 째 방법(Ford-Fulkerson)
생각:
가장 큰 흐름 의 템 플 릿 을 쓰 면 됩 니 다.
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1010;
const int inf = 0x7fffffff;
struct Edge {
int to;
int cap;
int rev;
Edge () {}
Edge (int to, int cap, int rev) : to(to), cap(cap), rev(rev) {}
};
vector g[maxn];
bool use[maxn];
int dfs(int v, int t, int f) {
if (v == t) return f;
use[v] = true;
for (int i = 0; i < g[v].size(); i++) {
Edge &e = g[v][i];
if (!use[e.to] && e.cap > 0) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int main() {
int n, m, t, from, to, cap;
scanf("%d", &t);
for (int Case = 1; Case <= t; Case++) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) g[i].clear();
while (m--) {
scanf("%d %d %d", &from, &to, &cap);
g[from].push_back(Edge(to, cap, g[to].size()));
g[to].push_back(Edge(from, 0, g[from].size() - 1));
}
int flow = 0;
while (1) {
memset(use, false, sizeof(use));
int f = dfs(1, n, inf);
if (f == 0) break;
flow += f;
}
printf("Case %d: %d
", Case, flow);
}
return 0;
}
두 번 째 방법(dinic)
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1010;
const int inf = 0x7fffffff;
struct Edge {
int to;
int cap;
int rev;
Edge () {}
Edge (int to, int cap, int rev) : to(to), cap(cap), rev(rev) {}
};
vector g[maxn];
int level[maxn];
bool use[maxn];
void bfs(int s) {
memset(level, -1, sizeof(level));
queue q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int i = 0; i < g[v].size(); i++) {
Edge &e = g[v][i];
if (level[e.to] < 0 && e.cap > 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
int dfs(int v, int t, int f) {
if (v == t) return f;
use[v] = true;
for (int i = 0; i < g[v].size(); i++) {
Edge &e = g[v][i];
if (level[v] < level[e.to] && e.cap > 0 && !use[e.to]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int main() {
int t, n, m, cap, to, from;
scanf("%d", &t);
for (int Case = 1; Case <= t; Case++) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) g[i].clear();
while (m--) {
scanf("%d %d %d", &from, &to, &cap);
g[from].push_back(Edge(to, cap, g[to].size()));
g[to].push_back(Edge(from, 0, g[from].size() - 1));
}
int flow = 0;
while (1) {
bfs(1);
if (level[n] < 0) break;
memset(use, false, sizeof(use));
int f = 0;
if ((f = dfs(1, n, inf)) > 0) {
flow += f;
}
}
printf("Case %d: %d
", Case, flow);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu4671(다교리그 7--수 시뮬레이션)클릭하여 링크 열기 제목: n과 서버, m개의 데이터베이스가 있고 모든 데이터베이스는 서버를 연결해야 하지만 모든 데이터베이스는 서버를 연결하는 우선순위가 있습니다.모든 데이터베이스의 서버 우선순위를 구하다.또한 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.