求助Dinic55pts
查看原帖
求助Dinic55pts
551861
strcmp楼主2022/1/27 10:32

测试点#4:

in:
200 1000 166 27
68 15 46
134 16 80
199 166 96
127 194 22
105 181 18
6 132 47
164 171 6
144 51 37
167 106 42
177 185 45
175 52 78
196 170 67
175 132 98
124 46 17
3 179 21
200 78 62
53 12 98
100 133 36
189 41 40
166 100 49
176 184 47
19 70 71
38 66 44
74 113 48
37 131 42
66 120 57
8 174 52
147 45 60
86 1 6
121 136 85
33 54 97
189 149 83
142 58 63
3 8 65
21 116 22
139 171 10
127 172 41
172 196 26
34 31 15
166 72 7
180 67 81
125 110 42
30 193 84
32 194 54
22 81 94
20 182 60
140 150 1
186 24 25
105 153 93
67 6 21
103 120 72
58 62 83
33 143 7
115 161 84
99 187 45
111 149 83
118 143 51
162 129 41
173 114 34
19 163 23
83 99 6
139 84 19
188 27 15
179 17 3
92 45 47
127 179 95
188 193 12
129 35 36
25 75 50
167 139 44
37 40 49
14 116 92
168 28 33
10 60 61
67 151 41
30 113 1
55 159 59
128 108 46
122 69 94
9 141 91
166 162 96
139 148 29
125 60 75
110 97 23
73 146 71
7 51 65
128 141 12
148 79 67
7 192 65
128 182 5
5 52 28
10 126 49
115 95 13
70 65 9
51 86 27
193 134 60
111 140 38
137 147 13
93 49 90
172 11 37
1 151 29
109 191 100
166 156 82
33 41 58
165 139 14
143 76 66
118 133 3
28 5 31
193 106 47
73 193 10
83 135 87
153 79 49
86 154 12
146 140 27
93 36 59
8 63 86
190 127 89
57 95 9
187 37 44
121 22 74
108 131 39
90 49 98
148 94 98
107 90 89
124 54 44
188 38 37
186 41 85
27 157 48
154 34 63
4 186 6
98 135 68
43 29 61
101 36 98
197 134 83
185 2 52
138 108 17
55 57 50
61 23 39
139 151 80
25 150 98
99 126 55
27 192 84
188 147 6
171 56 55
122 54 53
68 96 96
7 10 67
53 142 68
60 177 60
141 192 72
46 105 55
66 179 29
55 196 42
72 119 33
99 157 54
15 167 2
81 49 14
37 160 10
100 59 50
80 82 88
60 48 61
15 132 45
30 152 91
4 15 43
155 110 80
37 117 43
41 59 12
197 121 21
107 142 35
63 39 48
194 34 84
53 139 66
99 13 18
26 55 45
176 144 62
42 115 63
81 74 42
106 127 98
94 127 46
173 101 70
14 9 84
172 29 96
5 190 20
54 126 27
182 62 7
98 38 19
6 19 33
44 65 37
148 27 51
62 58 50
175 200 64
3 117 99
25 104 40
5 150 97
62 165 37
74 17 76
85 4 31
24 93 35
6 11 61
77 47 10
47 35 41
145 95 20
2 124 7
117 24 18
198 162 20
79 28 22
95 86 76
130 42 100
165 60 79
144 123 2
39 51 97
97 136 13
155 128 67
92 200 57
54 80 71
107 102 38
70 15 81
84 64 87
125 113 77
91 61 23
78 69 84
147 138 23
139 145 85
174 28 37
62 149 8
144 11 79
1 154 90
102 61 53
48 63 42
178 9 45
189 150 21
38 199 46
43 67 100
36 161 49
140 198 99
76 79 70
131 173 23
158 59 98
162 51 62
136 108 10
138 157 43
34 141 74
184 75 77
2 13 40
165 159 8
168 151 68
177 135 76
123 61 50
160 62 35
47 102 16
121 18 24
101 198 28
44 53 55
60 79 45
18 162 58
176 51 40
85 162 7
59 106 1
136 112 94
68 133 29
160 43 39
87 200 49
13 39 94
76 87 10
95 9 88
48 22 65
66 93 51
138 193 88
51 95 95
135 195 67
141 118 62
157 65 12
190 113 79
38 185 89
120 156 26
60 58 47
195 103 30
45 145 97
123 36 44
29 149 99
198 107 79
117 173 97
5 15 74
163 165 93
88 85 23
31 20 13
62 133 73
122 70 70
139 190 74
197 113 46
73 42 5
122 111 57
2 26 65
51 16 85
58 180 61
31 159 99
90 181 69
115 94 46
70 103 17
172 114 70
47 154 84
92 40 61
183 112 97
189 132 88
91 81 72
122 50 11
95 31 62
9 136 25
19 100 29
146 150 83
173 32 80
55 83 92
151 103 87
49 117 64
194 197 75
197 177 80
95 137 68
178 157 10
94 163 97
21 140 33
59 46 1
120 154 21
135 82 3
88 126 67
188 196 16
180 161 73
148 7 34
90 87 5
22 4 74
43 178 45
150 33 28
50 126 14
200 67 82
51 82 21
195 115 54
112 169 46
23 80 55
192 117 8
53 115 85
88 8 32
89 136 26
127 129 3
172 1 26
142 59 66
187 174 96
166 60 44
171 187 25
17 41 60
199 107 76
153 116 65
127 153 80
67 99 99
199 9 59
37 144 25
191 10 24
83 168 60
157 9 73
166 73 61
88 124 64
46 150 13
9 94 66
141 146 20
50 27 66
53 199 6
186 87 42
14 130 54
165 100 93
180 92 3
76 172 98
186 26 21
107 118 100
92 53 2
84 20 94
131 14 67
189 32 53
179 99 60
96 3 79
39 136 88
157 25 89
56 174 73
48 177 17
110 138 42
52 83 93
160 95 34
123 12 43
162 68 10
189 143 72
64 108 4
13 16 73
57 51 10
168 145 25
165 171 48
168 108 52
146 34 28
57 129 41
9 69 44
53 157 94
71 150 85
113 27 69
161 125 51
187 40 6
161 83 91
93 4 59
12 39 13
29 55 80
184 112 55
111 30 40
55 28 51
10 103 13
117 181 15
96 127 4
174 100 19
187 11 32
121 164 55
2 174 7
177 3 42
199 25 96
197 141 88
78 129 68
17 73 23
165 183 15
29 61 27
27 96 81
170 99 54
101 32 27
49 172 28
176 14 35
45 123 72
115 136 7
193 153 98
164 79 35
68 87 35
30 120 95
18 44 69
23 101 14
129 29 99
64 57 31
134 98 39
97 116 1
134 78 2
45 189 11
166 66 36
157 120 8
6 98 23
14 54 40
63 136 83
149 54 47
12 185 73
18 99 48
79 173 34
100 187 89
105 189 88
79 15 33
122 69 69
149 146 61
115 30 6
106 73 74
171 89 52
50 138 73
43 159 6
40 11 7
102 65 77
130 115 17
8 7 26
52 42 13
150 8 100
6 61 59
5 130 63
125 139 54
158 40 19
35 105 91
134 63 24
169 174 71
133 164 38
188 50 70
108 24 44
158 200 16
129 121 54
145 119 14
121 190 32
129 134 61
55 181 60
139 95 77
171 117 63
102 191 74
141 119 59
111 37 52
91 79 56
127 64 24
99 184 87
120 30 43
149 191 9
49 151 68
48 109 20
75 5 86
185 168 52
77 165 25
14 105 22
115 161 67
185 53 37
123 176 85
59 93 17
58 44 78
130 112 6
156 171 68
8 31 51
46 130 34
101 27 16
136 21 95
88 19 20
156 152 10
178 107 1
42 186 100
70 6 36
31 143 85
97 125 4
77 105 90
44 82 86
4 105 32
89 116 58
35 105 96
118 159 77
2 176 82
197 191 58
151 84 40
110 43 93
196 95 45
123 152 35
69 66 34
72 199 50
176 62 57
19 56 77
8 51 31
137 107 85
181 112 85
12 51 85
9 104 13
99 101 77
134 47 5
24 96 36
183 84 72
121 101 75
82 45 5
45 132 42
106 65 19
151 35 100
88 36 85
3 23 1
183 54 10
149 68 95
15 86 57
194 180 19
36 45 81
128 199 77
90 123 20
50 38 96
11 37 91
35 119 88
197 3 14
110 38 87
72 5 86
65 51 49
44 100 3
34 174 31
78 76 12
55 101 20
167 61 22
12 44 57
112 185 82
169 58 51
95 193 43
48 99 2
100 123 50
34 117 97
47 118 28
51 13 80
105 38 18
112 22 86
1 189 97
36 183 48
129 35 75
16 111 33
34 145 19
100 152 15
115 200 70
169 176 76
151 107 47
45 179 60
10 47 35
28 113 91
151 69 28
160 3 99
28 150 25
177 37 11
65 117 60
31 139 64
146 127 39
150 10 1
71 27 21
111 189 32
128 181 7
133 132 57
194 56 82
96 101 28
19 43 71
100 181 21
1 65 71
83 54 10
94 86 47
5 18 97
35 171 9
93 196 1
34 79 48
115 75 11
112 100 21
156 91 97
101 158 81
18 54 54
109 196 92
95 70 82
129 95 45
199 163 88
78 113 1
30 33 82
162 104 60
126 165 27
150 186 64
92 68 100
46 193 62
186 105 84
35 164 27
26 9 100
157 1 82
191 93 16
112 115 91
160 140 79
139 10 50
71 63 11
137 55 1
80 101 52
153 111 89
32 20 27
109 39 10
191 113 45
149 54 66
140 150 62
61 25 79
8 42 30
163 62 18
148 82 20
2 107 76
138 185 58
14 78 12
28 110 40
137 70 18
161 196 38
52 95 90
19 60 6
69 159 21
70 169 64
44 141 77
5 55 8
38 36 82
5 156 94
153 141 94
143 37 34
112 11 21
1 76 41
59 47 96
35 4 99
1 131 25
115 55 67
32 24 98
162 168 52
185 158 91
135 8 75
130 146 40
39 98 41
180 155 28
43 52 23
118 181 7
169 50 94
76 30 40
116 142 43
83 65 20
76 94 77
47 81 75
106 173 37
189 73 31
133 80 66
132 123 64
187 61 55
192 111 81
174 60 84
46 98 38
100 130 57
26 23 76
141 100 9
117 152 53
187 185 47
81 126 40
183 84 5
91 25 36
37 29 7
187 146 89
132 122 21
34 54 73
60 142 84
49 110 39
40 52 34
75 138 51
59 15 75
14 9 25
174 124 22
123 167 59
192 82 16
26 56 84
180 6 73
138 40 84
184 47 27
103 147 24
55 63 52
56 117 38
21 195 80
178 174 42
167 93 8
25 112 73
122 77 18
160 123 34
43 186 27
30 107 60
198 179 34
146 68 69
157 76 33
111 174 43
101 116 45
9 88 32
193 22 34
84 154 79
72 56 97
127 81 8
176 113 13
19 72 36
60 172 27
178 125 81
90 193 18
56 34 20
130 200 78
137 17 25
25 194 8
55 84 97
156 73 7
22 196 85
77 35 37
21 151 35
200 81 66
51 181 14
117 71 91
38 154 66
25 30 61
142 200 84
43 97 83
69 23 38
40 74 94
150 112 7
143 197 17
71 159 62
48 46 95
8 109 85
31 58 21
133 152 4
120 13 68
136 165 14
141 65 45
71 143 42
125 68 30
77 183 51
128 41 23
43 112 16
135 193 12
142 112 66
132 40 4
67 186 47
14 105 70
41 163 46
96 58 5
22 129 34
66 8 81
107 194 82
198 167 92
78 93 63
172 94 50
175 102 70
13 8 44
153 79 23
183 171 53
59 116 54
104 179 11
52 13 45
109 159 11
22 124 22
4 157 3
144 62 71
65 10 86
26 86 69
11 200 54
5 98 18
24 42 29
144 161 84
80 153 94
83 171 95
171 71 9
145 184 66
27 116 89
81 129 32
103 123 54
70 123 7
34 181 12
186 33 97
150 27 50
48 157 88
35 90 73
114 89 22
146 106 10
1 184 88
120 166 85
10 103 97
20 90 58
40 196 75
69 59 59
126 114 69
89 113 40
145 102 32
167 20 5
64 131 47
84 119 24
40 140 83
176 31 84
68 163 24
84 86 77
185 165 89
104 63 31
169 174 44
88 83 50
110 11 45
117 123 15
47 14 49
161 165 69
103 140 48
175 34 44
65 64 42
21 151 75
96 188 98
119 105 14
186 105 43
175 17 23
107 184 62
156 36 70
70 61 98
34 191 55
154 21 5
141 20 25
48 131 91
199 34 41
82 47 79
72 110 78
44 166 36
20 101 16
37 59 65
190 155 95
28 39 70
175 187 11
66 104 60
187 6 12
65 78 31
174 18 76
141 184 92
141 110 34
192 27 55
5 121 69
87 21 50
90 131 19
130 95 44
83 75 85
119 35 59
26 89 50
34 79 30
58 47 71
29 180 98
52 146 77
7 185 81
91 187 13
134 102 87
121 93 12
101 130 50
95 153 28
14 152 60
34 78 45
167 195 31
11 179 4
178 170 54
63 58 39
138 124 80
156 105 60
81 36 80
193 80 37
139 81 37
112 120 75
29 62 83
192 163 32
7 146 31
128 135 21
75 43 96
68 188 83
80 22 32
152 69 79
37 39 54
138 134 83
65 47 41
34 164 85
141 199 91
1 187 67
139 115 39
1 163 16
31 15 70
165 19 1
48 175 12
151 126 29
194 83 1
45 38 68
23 199 55
36 47 21
11 123 94
42 108 6
1 72 70
69 77 36
28 9 11
66 31 18
90 171 42
60 82 78
93 10 68
109 105 12
26 1 16
169 140 6
144 125 7
71 38 82
105 84 10
198 151 48
175 133 46
64 159 42
120 96 20
154 113 39
39 142 55
138 81 47
45 5 32
163 59 74
27 150 92
82 97 91
181 195 89
38 191 42
51 125 88
13 66 40
49 111 2
16 78 39
135 25 57
135 67 64
143 135 11
199 113 91
197 41 64
18 178 57
126 107 52
138 99 38
92 97 38
88 72 62
171 44 4
48 143 21
100 24 23
194 43 36
98 17 11
22 197 76
197 48 100
28 94 97
37 29 47
108 120 34
181 36 55
173 77 16
13 134 24
112 118 30
27 88 46
57 151 32
171 92 24
56 55 39
58 171 55
178 37 97
170 155 77
158 82 8
168 184 23
196 69 45
50 56 17
91 45 23

out:
321

我的Dinic输出是308

过样例+加强版样例+加强版测试点1

测试点#4,#7,#8WA ; #9,#10 TLE

请各位神犇们帮忙看看是哪里出了问题了,代码有简单注释,非常感谢!!!

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#define V 30000 //结点数
#define INF 99999999
using namespace std;
typedef long long int ll;//十年OI一场梦,不开ll见祖宗。
int n, m, s, t;//分别为 结点数n 边数m 源点编号s 汇点编号t
int thth, toto;//从thth到toto
ll howto;//权值为多少?
int head[V + 5];//head数组存结点
ll countnum = 0;//计数器

/*以下为Dinic算法重点*/
bool vis = true;//表示是否能到达汇点t
ll sum = 0;//存放总流量
bool isfind[V + 5];//为true表示已经遍历过了。
bool book[V + 5];
int levelset[V + 5];//保存层次
int nowlevel = 0;//目前的层次
int cur[V + 5];//cur[u]表示上次循环循环到了那条边 即Dinic算法的“当前弧优化”
queue<int>que1;//BFS队列1
queue<int>que2;//BFS队列2
int ls = 0;//目前历遍到的边的编号
/*以上为Dinic算法重点*/
struct edge {
public:
	int to;//到哪个结点
	ll capa;//容量
	ll flow;//流量
	ll resid;//残余流量
	int next;//next指针指向下一条边
	edge() = default;
	void init(int t, ll wei, int nexts = -1, int f = 0) {
		to = t;
		capa = wei;
		flow = f;
		resid = wei;
		next = nexts;
	}//加边
};//存边
vector<edge>edgeset;//内存池
void add(int first, int last, ll capacity, int f = 0) {
	if (head[first] != -1) {
		edgeset[countnum].init(last, capacity, head[first], f);
		head[first] = countnum;//头插
	}
	else { edgeset[countnum].init(last, capacity, -1, f); head[first] = countnum; }
	++countnum;
}//加边

/*以下为Dinic算法的核心代码*/
bool bfs() {
	for (int i = 1; i <= n; i++)cur[i] = head[i];
	que1.push(s);
	isfind[que1.front()] = true;
	while (!que1.empty()) {
		while (!que1.empty()) {
			levelset[que1.front()] = nowlevel;//更新层次
			isfind[que1.front()] = true;//标记已经找到了
			ls = head[que1.front()];//遍历边
			que1.pop();
			while (ls != -1) {//一直遍历到末尾
				if (book[edgeset[ls].to] == false && isfind[edgeset[ls].to] == false && edgeset[ls].resid > 0) {
					//只考虑未被发现的结点和残余边
					que2.push(edgeset[ls].to);
				}
				ls = edgeset[ls].next;
			}
		}
		while (!que2.empty()) {
			book[que2.front()] = true;
			que1.push(que2.front());
			que2.pop();
		}
		++nowlevel;//增加目前层次
	}
	bool isfindt = isfind[t];
	for (int i = 0; i <= n; i++)isfind[i] = false, book[i] = false;
	ls = 0;
	nowlevel = 0;
	return isfindt;
}//BFS构造层次图
ll dfs(int bh = s, ll a = INF) {//分别为当前结点编号bh和增广路径上的最小容量a
	if (bh == t) { vis = true; return a; }
	if (a == 0)return a;
	ll used = 0;//表示结点用了多少流量,方便多路增广
	ll ls = 0;
	for (int i = cur[bh]/*当前弧优化*/; i != -1; i = edgeset[i].next) {
		cur[bh] = i;
		if (levelset[bh] != levelset[edgeset[i].to]-1 || edgeset[i].resid==0)continue;
		ls = dfs(edgeset[i].to, min(a,edgeset[i].resid));
		if (ls != 0) {
			used += ls;
			if (used > a)used = a;
			edgeset[i].flow += ls;
			edgeset[i].resid -= ls;
			edgeset[i ^ 1].flow -= ls;
			edgeset[i ^ 1].resid += ls;
			if (used == a)break;
		}
	}
	return used;
}//DFS多路增广
ll Dinic()
{
	while (bfs()) {
		vis = true;
		while (vis) {
			vis = false;
			sum += dfs();
		}
	}
	return sum;
}//Dinic核心调用函数
/*以上为Dinic算法的核心代码*/
int main() {
	ios::sync_with_stdio(0);
	cin >> n >> m >> s >> t;
	edgeset.resize(m * 4);
	for (int i = 1; i <= n; i++)head[i] = -1;
	for (int i = 1; i <= m; i++) {
		cin >> thth >> toto >> howto;
		add(thth, toto, howto);//这个加正向弧
		add(toto, thth, 0, howto);//这个加反向弧
	}
	cout << Dinic();
	return 0;
}
2022/1/27 10:32
加载中...