图割Graph-Cut的最大流实现

清疚 2022-08-07 20:30 133阅读 0赞

利用最大流标号法求解最大流，详见代码：

Version：未加头尾节点版；

缺点:havn't take nodes' pixels into consideration

**\[cpp\]** [view plain][] [copy][view plain]

1.  /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/
2.  /\* MaxFlow solve graph cut program \*/
3.  /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/
4.  /\*
5.  File description:
6.  This program for graph cut based on Ford - Fulkerson Algorithm.
7.  Input: 
8.   M(edge number) N(node number)
9.   then M lines input 3 parameters each line:
10.  start\_point end\_point edge\_capacity
11.  e.g 5 4 1 4 40 1 2 20 2 4 10 4 3 30 3 2 10
12. output:
13.  Line 1:maxflow value
14.  Line2:nodes in Class 1
15.  e.g 
16.  MAX Flow is 50
17.  nodes in class S: 1 2
18. =========================================================================
19. CreateTime:2011-8-8
20. Author:@Zhang Ruiqing
21. \*/
22. \#include<iostream>
23. \#include<queue>
24. **using****namespace** std; 
25. \#define N 250//point
26. \#define M 250\*250//edge
27. \#define INF 1000000000
28. \#define min(a,b) a<b?a:b
29. 
30. **int** pre\[N\],map\[N\]\[N\]; 
31. **int** minlen\[N\];//minlen\[i\] represents min length from s to i
32. **int** pathmin\[N\];//min flow in this path from i to t
33. queue<**int**>Q; 
34. 
35. **int** n,m,s,t; 
36. 
37. **void** init(**int** s) 
38. \{ 
39.  memset(pre,0,**sizeof**(pre)); 
40. **for**(**int** i=0;i<=n;i++) 
41.  minlen\[i\]=pathmin\[i\]=INF; 
42.  minlen\[s\]=0; 
43. \} 
44. 
45. **bool** bfs(**int** s,**int** t) 
46. \{ 
47.  init(s); 
48. //push start node
49.  Q.push(s); 
50. **while**(!Q.empty()) 
51.  \{ 
52. **int** now=Q.front(); 
53.  Q.pop(); 
54. **for**(**int** i=1;i<=n;i++) 
55.  \{ 
56. **if**(map\[now\]\[i\]!=0&&minlen\[now\]+map\[now\]\[i\]<minlen\[i\]) 
57.  \{ 
58.  minlen\[i\]=minlen\[now\]+map\[now\]\[i\]; 
59.  pre\[i\]=now; 
60.  pathmin\[i\]=min(pathmin\[now\],map\[now\]\[i\]); 
61.  Q.push(i); 
62.  \} 
63.  \} 
64.  \} 
65. **if**(minlen\[n\]==INF) 
66. **return****false**; 
67. **return****true**; 
68. \} 
69. 
70. **int** max\_flow(**int** s,**int** t) 
71. \{ 
72. **int** res=0; 
73. **while**(bfs(s,t))//if can find an augment road
74.  \{ 
75. **int** minflow=pathmin\[n\];//minimal flow in the path
76. **int** point=t;//calculate from end point t to start point s
77. **while**(point!=s) 
78.  \{ 
79. **int** prep=pre\[point\]; 
80.  map\[prep\]\[point\]-=minflow;//positive road -= flow
81.  map\[point\]\[prep\]+=minflow;//nagative road+= flow
82.  point=prep; 
83.  \} 
84.  res+=minflow; 
85.  \} 
86. **return** res; 
87. \} 
88. 
89. **int** main() 
90. \{ 
91. **int** i,j; 
92. **int** a,b,c; 
93. **while**(scanf("%d%d",&m,&n)!=EOF) 
94.  \{ 
95.  memset(map,0,**sizeof**(map)); 
96. **for**(i=0;i<m;i++) 
97.  \{ 
98.  cin>>a>>b>>c; 
99.  map\[a\]\[b\]+=c; 
100.  \} 
101.  s=1; 
102.  t=n; 
103.  cout<<"MAX Flow is "<<max\_flow(s,t)<<endl; 
104. 
105.  cout<<"nodes in class S: 1 "; 
106. **for**(i=0;i<n;i++) 
107.  \{ 
108. **if**(pathmin\[i\]!=INF) 
109.  cout<<i<<" "; 
110.  \} 
111.  cout<<endl; 
112.  \} 
113. **return** 0; 
114. \}

[view plain]: http://blog.csdn.net/abcjennifer/article/details/6668913#