題意：
? ? ? 給你一個平面圖，要求從求出從左上角到右下角的最小割。
思路：

? ? ? 如果大意的可能直接上來一遍最大流，然后就會各種悲劇的MLE，TLE，其實這個題目可以用到有個論文里面的那個平面圖最小割轉最短路(hdu3870 也是這種問題)，我們證明說著費勁直接給一個圖片理解就行了，思路就是這張圖片

這個題目用Spfa會超時的，要用優化過的Dij才能過，我不會的優化過的Dij，直接用模板過的。

#include<stdio.h> #include<string.h> #include<queue> using namespace std;//************************************************* #include<queue> #define FOR(i,a,b) for(int i=a;i<=b;++i) #define clr(f,z) memset(f,z,sizeof(f)) #define LL long long using namespace std;const int mm=1e6+9; const LL oo=1e16; class Edge {public:int v,next;LL w; }; class Dot {public:LL dis;int v;Dot(){}Dot(int _v,LL _d){v=_v;dis=_d;}bool operator<(const Dot&x)const{return dis>x.dis;} }; class ShortPath {public:int head[mm],edge;Edge e[3000000];void clear(){clr(head,-1);edge=0;}void add(int u,int v,LL w){e[edge].v=v;e[edge].w=w;e[edge].next=head[u];head[u]=edge++;}bool vis[mm];int id[mm];LL dis[mm];priority_queue<Dot>Q;LL dijstra(int s,int t,int n){int u,v;Dot uu;FOR(i,0,n)dis[i]=oo,vis[i]=0;Q.push(Dot(s,0));dis[s]=0;while(!Q.empty()){uu=Q.top();Q.pop();u=uu.v;if(vis[u])continue;vis[u]=1;for(int i=head[u];~i;i=e[i].next){ v=e[i].v;if(!vis[v]&&dis[v]>dis[u]+e[i].w){dis[v]=dis[u]+e[i].w;Q.push(Dot(v,dis[v]));}}}return dis[t];} }sf;//sf.clear(); //sf.add(); //sf.dijstra(s ,t ,n); //******************************** int main () {int n ,m ,i ,j ,a ,b ,now ,p1 ,p2 ,p3 ,p4;while(~scanf("%d %d" ,&n ,&m)){int s = 0 ,t = n * m * 4 + 1;sf.clear();for(i = 1 ;i <= n + 1;i ++)for(j = 1 ;j <= m ;j ++){scanf("%d" ,&a);now = (i - 1) * m + j;p1 = (now - 1) * 4 + 1;p2 = (now - 1) * 4 + 2;p3 = (now - 1) * 4 + 3;p4 = (now - 1) * 4 + 4;if(i == 1) sf.add(s ,p2 ,a);else if(i == n + 1) {int p44 = ((i - 1 - 1) * m + j - 1) * 4 + 4;sf.add(p44 ,t ,a);}else {int noww = now - m;sf.add(p2 ,(noww - 1) * 4 + 4 ,a);sf.add((noww - 1) * 4 + 4 ,p2 ,a); } }for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m + 1 ;j ++){scanf("%d" ,&a);now = (i - 1) * m + j;p1 = (now - 1) * 4 + 1;p2 = (now - 1) * 4 + 2;p3 = (now - 1) * 4 + 3;p4 = (now - 1) * 4 + 4;if(j == 1) sf.add(p1 ,t ,a);else if(j == m + 1){int p33 = ((i - 1) * m + j - 1 - 1) * 4 + 3;sf.add(s ,p33 ,a);}else{int noww = now - 1;sf.add(p1 ,(noww - 1) * 4 + 3 ,a);sf.add((noww - 1) * 4 + 3 ,p1 ,a); }}for(i = 1 ;i <= n * 2 ;i ++)for(j = 1 ;j <= m ;j ++){scanf("%d %d" ,&a ,&b);int ii = (i + 1) / 2;now = (ii - 1) * m + j;p1 = (now - 1) * 4 + 1;p2 = (now - 1) * 4 + 2;p3 = (now - 1) * 4 + 3;p4 = (now - 1) * 4 + 4;if(i & 1){sf.add(p1 ,p2 ,a) ,sf.add(p2 ,p1 ,a);sf.add(p2 ,p3 ,b) ,sf.add(p3 ,p2 ,b);}else{sf.add(p3 ,p4 ,b) ,sf.add(p4 ,p3 ,b);sf.add(p4 ,p1 ,a) ,sf.add(p1 ,p4 ,a);}}printf("%d\n" ,sf.dijstra(s ,t ,t));}return 0; }

總結

以上是生活随笔為你收集整理的hdu3035 最小割转换成最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。