UVAOJ 1515 Pool construction

給每個格子一個點
連到s代表選地，連到t代表選洞
相鄰的再連一條cost為b的無向邊
做最大流

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define INF 10000000
using namespace std;
typedef long long int int64;
struct{ int a, b, val; }lks[100000]; int lks_cnt;
vector<int> to[100000];
int _n;
void init(int n){
 _n = n;
 for(int lx = 0;lx < n;lx++){
  to[lx].clear();
 }
 lks_cnt = 0;
 return;
}
void addlink(int a, int b, int ab){
 //printf("link %d -> %d with %d\n", a, b, ab);
 lks[lks_cnt].a = a, lks[lks_cnt].b = b, lks[lks_cnt].val = ab; to[a].push_back(lks_cnt++);
 lks[lks_cnt].a = b, lks[lks_cnt].b = a, lks[lks_cnt].val = 0; to[b].push_back(lks_cnt++);
 return;
}
int dis[100000], que[100000] ;
int bfs(int s, int t){
 int n = _n;
 for(int lx = 0;lx < n;lx++){
  dis[lx] = -1;
 }
 dis[s] = 0;
 int qs = 0, qe = 1;
 que[0] = s;
 while(qs < qe){
  int g = que[qs++];
  for(int lx = 0;lx < to[g].size();lx++){
   int lind = to[g][lx];
   int pind = lks[lind].b;
   if(dis[pind] != -1) continue;
   if(lks[lind].val == 0) continue;
   dis[pind] = dis[g]+1;
   que[qe++] = pind;
  }
 }
 return (dis[t] != -1);
}
bool vis[100000];
int dfs(int vv, int df, int s, int t){
 //printf("dfs: %d\n", vv);
 //for(int lx = 0;lx/100000 < 100;lx++);
 if(vv == t) return df;
 if(vis[vv]) return 0;
 vis[vv] = true;
 for(int lx = 0;lx < to[vv].size();lx++){
  int lind = to[vv][lx];
  int pind = lks[lind].b;
  if(lks[lind].val == 0) continue;
  if(dis[pind] != dis[vv] +1) continue;
  int f = dfs(pind, min(df, lks[lind].val), s, t);
  if(f > 0){
   lks[lind].val -= f;
   lks[lind^1].val += f;
   return f;
  }
 }
 return 0;
}
int dinic(int s, int t){
 int f = 0, df = 0;
 while(bfs(s, t))
  for(;;){
   memset(vis, 0, sizeof(vis));
   int df = dfs(s, 1000000000, s, t);
   if(df == 0) break;
   f += df;
  }
 return f;
}
int ctr = 0; int get_ind(){return ctr++;}
int main()
{
 int T;scanf("%d", &T);
 while(T--){
  int w, h; scanf("%d %d", &w, &h);
  int d, f, b;scanf("%d %d %d", &d, &f, &b);
  int Map[60][60];
  for(int lx = 0;lx < h;lx++){
   char str[1000];
   scanf("%s", str);
   for(int ly = 0;ly < w;ly++)
    Map[lx][ly] = str[ly] == '#';
  }

  ctr = 0;
  int ss = get_ind(), tt = get_ind();
  int map_nod[100][100];
  for(int lx = 0;lx < h;lx++)
   for(int ly = 0;ly < w;ly++)
    map_nod[lx][ly] = get_ind();
  int ind_count = get_ind();
  init(ind_count);
  for(int lx = 0;lx < h;lx++){
   for(int ly = 0;ly < w;ly++) {
    if((lx == 0) or (lx == h-1) or (ly == 0) or (ly == w-1)){
     if(Map[lx][ly]){
      addlink(map_nod[lx][ly], tt, INF);
     }else{
      addlink(ss, map_nod[lx][ly], f);
      addlink(map_nod[lx][ly], tt, INF);
     }
    }else{
     if(Map[lx][ly]){
      addlink(map_nod[lx][ly], tt, d);
     }else{
      addlink(ss, map_nod[lx][ly], f);
     }
    }
   }
  }
  for(int lx = 0;lx < h-1;lx++){
   for(int ly = 0;ly < w;ly++){
    //down
    addlink(map_nod[lx][ly], map_nod[lx+1][ly], b);
    addlink(map_nod[lx+1][ly], map_nod[lx][ly], b);
   }
  }
  for(int lx = 0;lx < h;lx++){
   for(int ly = 0;ly < w-1;ly++){
    //down
    addlink(map_nod[lx][ly], map_nod[lx][ly+1], b);
    addlink(map_nod[lx][ly+1], map_nod[lx][ly], b);
   }
  }
  printf("%d\n", dinic(ss, tt));
 }
 return 0;
}