UVA1515 pool ,玄学的最小割

Posted by Cww97 on 2016-10-05

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52736469
白书题,,,,不是很理解最小割u
多刷题吧,
以后应该就会了

这里写图片描述
这里写图片描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int dx[]={ 0, 0,-1, 1};
const int dy[]={-1, 1, 0, 0};
const int INF=0x3f3f3f3f;
const int N = 9999;
int n,m,a[N],b[N];

struct Dinic{
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):
from(u),to(v),cap(c),flow(f){}
};
int n, s, t;
vector<Edge>edges;
vector< int>G[N]; //gragh
bool vis[N]; //use when bfs
int d[N],cur[N];//dist,now edge,use in dfs
inline void AddEdge(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from, 0 ,0));
int top = edges.size() ;
G[from].push_back(top-2);
G[ to ].push_back(top-1);
}
inline void Init(int n){
this -> n= n ;
s = 0, t = n ;
edges.clear();
for (int i=0;i<=n;i++)G[i].clear();
}

inline bool BFS(){
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(s);d[s]=0;vis[s]=1;
while (!Q.empty()){
int x=Q.front();Q.pop();
for (int i=0;i<G[x].size();i++){
Edge &e=edges[G[x][i]];
if (vis[e.to]||e.cap<=e.flow)continue;
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
return vis[t];
}
inline int DFS(const int& x,int a){
if (x==t||a==0){return a;}
int flow = 0, f;
for (int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if (d[x]+1!=d[e.to])continue;
if ((f=DFS(e.to,min(a,e.cap-e.flow)))<=0)continue;
e.flow += f;
edges[G[x][i]^1].flow-=f;//ϲߍ
flow+=f; a-=f;
if (!a) break;
}
return flow;
}
inline int maxFlow(){return maxFlow(s,t);}
inline int maxFlow(const int& s,const int& t){
int flow=0;
while(BFS()){
memset(cur,0,sizeof(cur));
flow += DFS(s,INF) ;
//printf("flow=%d\n",flow);
}
return flow;
}
} g ;

bool pool[99][99];
int id[99][99];
int main(){
//freopen("in.txt","r",stdin);
int T,n,m,d,f,b;
scanf("%d", &T);
for (char ch;T--;){
scanf("%d%d%d%d%d\n",&m,&n,&d,&f,&b);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
scanf("%c",&ch);
pool[i][j] = ch=='#';
id[i][j] = (i-1)*m+j;
}
getchar() ;
}
int ans = 0;
g.Init( n*m+1);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (i==1||i==n||j==1||j==m){
g.AddEdge(g.s,id[i][j],INF);
if (!pool[i][j]) ans += f ;
}else{//not at the bounder
if(pool[i][j])g.AddEdge(g.s,id[i][j],d);
else g.AddEdge(id[i][j],g.t,f);
}
for (int k=0;k<4;k++){
int cx = i + dx[k];
int cy = j + dy[k];
if (cx<1||cx>n||cy<1||cy>m)continue;
g.AddEdge(id[i][j],id[cx][cy],b);
}
}
}
printf("%d\n", ans + g.maxFlow());
}
return 0;
}