生活随笔
收集整理的這篇文章主要介紹了
Pool construction UVA - 1515 最小割模型
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
傳送門
文章目錄
題意：
給你一個n?mn*mn?m的矩陣，包含字符#和.，將#變成.的代價是ddd，將.變成#的代價是fff，讓后將#和.隔開的代價是bbb，現在讓你用最小的代價將#和.隔開，并且矩陣邊界必須是#。
n,m≤50n,m\le 50n,m≤50
思路：
看到將兩部分分開，自然的想到最小割的概念，所以引入源點和匯點考慮建圖。
首先是將源點與#連容量為ddd的邊，代表將#變成.的代價，割掉說明將#變成了.。
將.與匯點連代價是fff的邊，意義同上。
需要注意的是，在邊界上的#需要從匯點向其連一個容量為INFINFINF的邊，代表其不能被變成.。
還需要將每個點向其周圍連容量為bbb的邊，如果四周某個點與其相同，邊的含義是如果將其改變，即割掉源點跟他之間的邊，那么還需要割掉原本跟他相同的之間的邊。如果四周某個點跟他不同，邊的含義是如果不改變，需要割掉他們倆之間的邊。
讓后直接建圖跑就好啦。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=100010,M
=N
*2,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,m
;
char s
[110][110];
int d
,f
,b
;
struct Maxflow
{int n
,m
,S
,T
;int e
[M
],ne
[M
],w
[M
],h
[N
],hs
[N
],idx
;int depth
[N
];void init() { idx
=0; memset(h
,-1,sizeof (h
)); }inline void add(int a
,int b
,int c
){e
[idx
]=b
,w
[idx
]=c
,ne
[idx
]=h
[a
],h
[a
]=idx
++;e
[idx
]=a
,w
[idx
]=0,ne
[idx
]=h
[b
],h
[b
]=idx
++;}bool bfs(){memset(depth
,-1,sizeof (depth
)); depth
[S
]=0;queue
<int>q
; q
.push(S
); hs
[S
]=h
[S
];while(q
.size()){int t
=q
.front(); q
.pop();for(int i
=h
[t
];~i
;i
=ne
[i
]){int ver
=e
[i
];if(depth
[ver
]==-1&&w
[i
]>0){depth
[ver
]=depth
[t
]+1;hs
[ver
]=h
[ver
];if(ver
==T
) return true;q
.push(ver
);}}}return false;}int dfs(int u
,int flow
){if(u
==T
) return flow
;int d
=flow
;for(int i
=hs
[u
];~i
;i
=ne
[i
]){int ver
=e
[i
]; hs
[u
]=i
;if(depth
[ver
]==depth
[u
]+1&&w
[i
]>0){int t
=dfs(ver
,min(w
[i
],d
));if(!t
) depth
[ver
]=-1;d
-=t
; w
[i
]-=t
; w
[i
^1]+=t
;if(!d
) break;}}return flow
-d
;}int dinic(){int ans
=0,flow
;while(bfs()) while(flow
=dfs(S
,INF
)) ans
+=flow
;return ans
;}
}MF
;
int dir
[4][2]={1,0,-1,0,0,1,0,-1};int get(int i
,int j
) {return (i
-1)*m
+j
;
}int main()
{
int _
; scanf("%d",&_
);while(_
--) {scanf("%d%d%d%d%d",&m
,&n
,&d
,&f
,&b
);for(int i
=1;i
<=n
;i
++) scanf("%s",s
[i
]+1);int ans
=0;for(int i
=1;i
<=n
;i
++) {if(s
[i
][1]=='.') s
[i
][1]='#',ans
+=f
;if(s
[i
][m
]=='.') s
[i
][m
]='#',ans
+=f
;}for(int i
=1;i
<=m
;i
++) {if(s
[1][i
]=='.') s
[1][i
]='#',ans
+=f
;if(s
[n
][i
]=='.') s
[n
][i
]='#',ans
+=f
;}MF
.init(); MF
.S
=N
-1,MF
.T
=N
-2;for(int i
=1;i
<=n
;i
++) {for(int j
=1;j
<=m
;j
++) {if(s
[i
][j
]=='#') {if(i
==1||j
==1||i
==n
||j
==m
) MF
.add(MF
.S
,get(i
,j
),INF
);else MF
.add(MF
.S
,get(i
,j
),d
);}else MF
.add(get(i
,j
),MF
.T
,f
);for(int k
=0;k
<4;k
++) {int dx
=i
+dir
[k
][0];int dy
=j
+dir
[k
][1];if(dx
<1||dy
<1||dx
>n
||dy
>m
) continue;MF
.add(get(i
,j
),get(dx
,dy
),b
);}}}ans
+=MF
.dinic();printf("%d\n",ans
);}return 0;
}
總結
以上是生活随笔為你收集整理的Pool construction UVA - 1515 最小割模型的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
