XieNaoban's Blog
0%

UVA11248 - Frequency Hopping (网络流)

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 3.1k 阅读时长 ≈ 3 分钟

Description

uva的pdf格式题目复制有问题，直接贴原题链接了。 UVA11248 - Frequency Hopping

Key

给一个N点E条边的网络流，问能否找出1->N的一条流量等于C的流。若不能，若修改一条弧的上界，可否找到？列出所有可修改的弧。

先求出最大流，若大于C，输出“possible”。 若小于C，枚举修改每一条弧再次运行最大流（记得记录每条修改过的弧，本次最大流运行过后再重新把每条弧的流量恢复。不能每次都从头开始计算最大流，会超时）。

可以如下优化，不需要求最大流，只需流量大于等于C时就可以停止。不过既然已经AC了就不管了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;

#define INF 0x3f3f3f3f

struct UIF {
	int u, i, f;
	UIF(const int &u, const int &i, const int &f) :u(u), i(i), f(f) {}
};

const int Maxn = 150;
typedef pair<int, int> UV;
int N, E, C;
vector<UV> Q;
vector<UIF> Chg;

struct Edge {
	int c, f;
	unsigned v, flip;
	Edge(unsigned v, int c, int f, unsigned flip) :v(v), c(c), f(f), flip(flip) {}
};

class Dinic {
private:
	bool b[Maxn];
	int a[Maxn];
	unsigned p[Maxn], cur[Maxn], d[Maxn];

public:
	vector<Edge> G[Maxn];
	unsigned s, t;
	void Init(unsigned n) {
		for (int i = 0; i <= n; ++i)
			G[i].clear();
	}

	void AddEdge(unsigned u, unsigned v, int c) {
		G[u].push_back(Edge(v, c, 0, G[v].size()));
		G[v].push_back(Edge(u, 0, 0, G[u].size() - 1));	//使用无向图时将0改为c即可 
	}

	bool BFS() {
		unsigned u, v;
		queue<unsigned> q;
		memset(b, 0, sizeof(b));
		q.push(s);
		d[s] = 0;
		b[s] = 1;
		while (!q.empty()) {
			u = q.front();
			q.pop();
			for (auto it = G[u].begin(); it != G[u].end(); ++it) {
				Edge &e = *it;
				if (!b[e.v] && e.c > e.f) {
					b[e.v] = 1;
					d[e.v] = d[u] + 1;
					q.push(e.v);
				}
			}
		}
		return b[t];
	}

	int DFS(unsigned u, int a) {
		if (u == t || a == 0)
			return a;
		int flow = 0, f;
		for (unsigned &i = cur[u]; i < G[u].size(); ++i) {
			Edge &e = G[u][i];
			if (d[u] + 1 == d[e.v] && (f = DFS(e.v, min(a, e.c - e.f))) > 0) {
				a -= f;
				e.f += f;
				G[e.v][e.flip].f -= f;
				flow += f;
				Chg.push_back(UIF(u, i, f));
				Chg.push_back(UIF(e.v, e.flip, -f));
				if (!a) break;
			}
		}
		return flow;
	}

	int MaxFlow(unsigned s, unsigned t) {
		int flow = 0;
		this->s = s;
		this->t = t;
		while (BFS()) {
			memset(cur, 0, sizeof(cur));
			flow += DFS(s, INF);
			//if (flow >= C) break;
		}
		return flow;
	}
};

void Traverse(Dinic &din, int lf) {
	for (int u = 1; u <= N; ++u) {
		for (auto &e : din.G[u]) if (e.c) {
			int tmp = e.c;
			e.c = C;
			Chg.clear();
			int f = din.MaxFlow(1, N);
			if (f >= lf) Q.push_back(make_pair(u, e.v));
			e.c = tmp;
			for (const auto &e : Chg) din.G[e.u][e.i].f -= e.f;
		}
	}
}

int main() {
	int Case = 0;
	while (~scanf("%d%d%d", &N, &E, &C) && (N | E | C)) {
		Dinic Din;
		int u, v, c;
		for (int i = 1; i <= E; ++i) {
			scanf("%d%d%d", &u, &v, &c);
			Din.AddEdge(u, v, c);
		}
		int f = Din.MaxFlow(1, N);
		printf("Case %d: ", ++Case);
		if (f >= C) {
			puts("possible");
		}
		else {
			Q.clear();
			Traverse(Din, C - f);
			if (Q.empty()) {
				puts("not possible");
			}
			else {
				printf("possible option:");
				sort(Q.begin(), Q.end());
				for (auto p = Q.begin(); p != Q.end(); ++p) {
					printf("(%d,%d)%c", p->first, p->second, ",\n"[p + 1 == Q.end()]);
				}
			}
		}
	}
}