题目： http://61.187.179.132/JudgeOnline/problem.php?id=1001
最小割转化为平面图最短路问题
具体方法：
将每个三角形看作节点，连双向边：
1.S->最左边一列三角形，边权为该三角形的左边流量；
2.S->最下边一列三角形，边权为该三角形的下边流量；
3.最右边一列三角形->T，边权为该三角形的右边流量；
4.最上边一列三角形->T，边权为该三角形的上边流量；
5.三角形->左边连着的三角形，边权为公共边流量；
6.三角形->下边连着的三角形，边权为公共边流量；
7.三角形->右边连着的三角形，边权为公共边流量。
然后SPFA求最短路
1
#include <iostream>
2#include <cstring>
3#include <cstdlib>
4#include <cstdio>
5using namespace std;
6const int MaxN=1050;
7const int MaxM=1050;
8const int MaxMN=2*MaxN*MaxM;
9const int MaxT=MaxMN*3;
10const int oo=10000001;
11
12int next[MaxT],head[MaxMN],c[MaxT],node[MaxT];
13int n,m,t=0,S=0,T;
14int d[MaxMN];
15int q[MaxMN];
16bool v[MaxMN];
17
18void add(int a,int b,int v)
19
{
20
node[t]=b;
21 c[t]=v;
22 next[t]=head[a];
23 head[a]=t;
24 t++;
25 node[t]=a;
26 c[t]=v;
27 next[t]=head[b];
28 head[b]=t;
29 t++;
30// cout<<"A"<<a<<' '<<b<<' '<<v<<endl;
31
}
32
33void init()
34{
35 scanf("%d%d",&n,&m);
36
37 //初始化
38 T=(n-1)*(m-1)*2+1;
39 int s;
40 memset(next,-1,sizeof(next));
41 memset(head,-1,sizeof(head));
42
43 //读第一部分
44 for (int j=1;j<=m-1;j++)
45
{
46 scanf("%d",&s);
47 add(2*j,T,s);
48
}
49 for (int i=2;i<=n-1;i++)
50 {
51 for (int j=1;j<=m-1;j++)
52 {
53 scanf("%d",&s);
54 add((i-2)*(m-1)*2+2*j-1,(i-1)*(m-1)*2+2*j,s);
55 }
56 }
57 for (int j=1;j<=m-1;j++)
58 {
59 scanf("%d",&s);
60 add(S,(n-2)*(m-1)*2+2*j-1,s);
61 }
62
63 //读第二部分
64 for (int i=1;i<=n-1;i++)
65 {
66 scanf("%d",&s);
67 add(S,(i-1)*(m-1)*2+2*1-1,s);
68 for (int j=2;j<=m-1;j++)
69 {
70 scanf("%d",&s);
71 add((i-1)*(m-1)*2+2*j-1-1,(i-1)*(m-1)*2+2*j-1,s);
72 }
73 scanf("%d",&s);
74 add((i-1)*(m-1)*2+2*(m-1),T,s);
75 }
76
77 //读第三部分
78 for (int i=1;i<=n-1;i++)
79 {
80 for (int j=1;j<=m-1;j++)
81 {
82 scanf("%d",&s);
83 add((i-1)*(m-1)*2+2*j-1,(i-1)*(m-1)*2+2*j,s);
84 }
85 }
86}
87
88int dijkstra()
89{
90 for (int i=S;i<=T;i++)
91 {
92 d[i]=oo;
93 v[i]=0;
94 }
95 d[S]=0;
96 int minm=0;
97 for (;d[T]==oo || minm==-1;)
98 {
99 minm=-1;
100 for (int i=S;i<=T;i++)
101 {
102 if (v[i]==0)
103 {
104 if ((minm==-1) || (d[i]<d[minm]))
105 {
106 minm=i;
107 }
108 }
109 }
110 v[minm]=1;
111 for (int i=head[minm];i!=-1;i=next[i])
112 {
113 if (d[node[i]]>d[minm]+c[i])
114 {
115 d[node[i]]=d[minm]+c[i];
116 }
117 }
118 //cout<<minm<<endl;
119 //system("pause");
120 }
121 return d[T];
122}
123
124int spfa()
125{
126 for (int i=S;i<=T;i++)
127 {
128 d[i]=oo;
129 v[i]=0;
130 }
131 d[S]=0;
132 v[S]=1;
133 q[0]=S;
134 for (int first=0,last=1;first!=last;first++)
135 {
136 if (first>=MaxMN) first-=MaxMN;
137 v[q[first]]=0;
138 for (int i=head[q[first]];i!=-1;i=next[i])
139 {
140 if (d[node[i]]>d[q[first]]+c[i])
141 {
142 d[node[i]]=d[q[first]]+c[i];
143 if (v[node[i]]==0)
144 {
145 v[node[i]]=1;
146 q[last++]=node[i];
147 if (last>=MaxMN) last-=MaxMN;
148 }
149 }
150 }
151 }
152 return d[T];
153}
154
155int main()
156{
157 init();
158 printf("%d\n",spfa());
159 return 0;
160}
161
162
163