UVA1515 pool ，玄学的最小割

白书题，，，，不是很理解最小割u
多刷题吧，
以后应该就会了

#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
",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
",&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
", ans + g.maxFlow());
    }
    return 0;
}