坑！-tower

题目链接：https://cn.vjudge.net/contest/281959#problem/E

建图真真完全没搞懂，，照着题解不知道咋回事就过了。。。

不想看了留坑开学后再说吧

参考题解：https://www.cnblogs.com/hongyj/p/8646446.html
https://blog.csdn.net/qq_33229466/article/details/70159372

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
struct node
{
    int next,to,dis;
}edge[600030];
int head[100010],cur[100010],deep[100010];
int n,m,cnt=2,maxflow;
int nextt[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
///核心代码无需改动--start
void addedge(int from,int to,int dis)
{
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    edge[cnt].next=head[from];
    head[from]=cnt++;

    edge[cnt].to=from;
    edge[cnt].dis=0;
    edge[cnt].next=head[to];
    head[to]=cnt++;
}

bool bfs(int s,int t)
{
    memset(deep,0,sizeof(deep));
    queue<int>q;
    while(!q.empty())
        q.pop();
    memcpy(cur,head,sizeof(head));
    deep[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i!=-1;i=edge[i].next)
        {
            if(!deep[edge[i].to]&&edge[i].dis)
            {
                deep[edge[i].to]=deep[now]+1;
                q.push(edge[i].to);
            }
        }
    }
    return deep[t];
}

int dfs(int now,int t,int limit)
{
    if(!limit||now==t)
        return limit;
    int flow=0;
    for(int i=cur[now];i!=-1;i=edge[i].next)
    {
        if(edge[i].dis&&deep[edge[i].to]==deep[now]+1)
        {
            int d=dfs(edge[i].to,t,min(limit,edge[i].dis));
            flow+=d;
            limit-=d;
            edge[i].dis-=d;
            edge[i^1].dis+=d;
        }
    }
    if(!flow)deep[now]=0;
    return flow;
}


void dinic(int s,int t)
{
    while(bfs(s,t))
        maxflow+=dfs(s,t,inf);
}
///核心代码--end
int hashh[111][111],tot=0,mp[111][111];

int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    int summ=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            hashh[i][j]=++tot;
            cin>>mp[i][j];
        }
    }
    cnt=2;
    int s,t;
    s=0;
    t=tot*2+1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(mp[i][j]<0)
            {
                int mx=0;
                int tx=i,ty=j;
                int op=-mp[i][j]-1;
                while(1)
                {
                    tx+=nextt[op][0];
                    ty+=nextt[op][1];
                    if(tx>n||ty>m||!tx||!ty)
                        break;
                    mx=max(mx,mp[tx][ty]);
                }
                summ+=mx;
                if(op<2)
                    addedge(s,hashh[i][j],inf);
                else addedge(tot+hashh[i][j],t,inf);
                tx=i;
                ty=j;
                while(1)
                {
                    int lp=tx,lq=ty;
                    tx+=nextt[op][0];
                    ty+=nextt[op][1];
                    if(tx>n||ty>m||!tx||!ty)
                        break;
                    if(op<2)addedge(hashh[lp][lq],hashh[tx][ty],mx-max(0,mp[lp][lq]));
                    else addedge(hashh[tx][ty]+tot,hashh[lp][lq]+tot,mx-max(mp[lp][lq],0));
                }
            }
            else addedge(hashh[i][j],tot+hashh[i][j],inf);
        }
    }
    maxflow=0;
    dinic(s,t);
    cout<<summ-maxflow<<endl;
    return 0;
}