题解：CF1955H The Most Reckless Defense

· · 题解

为什么所有题解都是状压 DP ，这题不是看着很网络流（最小费用最大流）吗？

首先还是分析一下 r 的取值范围，可以把敌人增加的血量理解为减少防御塔的伤害，那么一座防御塔的总伤害最多是 500\pi r^2 - 3^r，不难发现 r 最大为 12，这就很符合网络流的范围。

接下来建图，把防御塔当作左部点，半径为右部点。有几种类型的边：

第 1 类：源点向左部点连边，流量为 1，费用为 0。

第 2 类：右部点向汇点连边，流量为 1，费用为 0。

第 3 类：每一个左部点向每一个右部点连边，流量为 1，费用为这座防御塔在这个半径下的总伤害（减去了敌人增加的血量）的相反数。

对第 3 类边做一下解释：

费用流求的是最小费用，但是我们要求的是最大的伤害，所以取一个相反数，输出的时候反过来就行了。当然如果本来就是个负数肯定不连。

代码：

/*网络流千万想清楚清空！！！！！！！！！！！！！*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=400010;
const int INF=10000000000000000;
int t,n,m,k,s,tt;
int used[N];
int pw[20];
int ct;
struct stu{
    int x,y;
}road[N];

struct node{
    int x,y,p;
}tow[N];

int ans;

namespace EK{
    int nxt[N],dis[N],cost[N],to[N],head[N],flow[N];
    int pre[N],increase[N];
    bool vis[N];
    int tot=1;
    void add(int x,int y,int z,int c){
        to[++tot]=y;
        flow[tot]=z;
        cost[tot]=c;
        nxt[tot]=head[x];
        head[x]=tot;
    }
    bool spfa(){
        for(int i=0;i<=t;i++){
            dis[i]=INF;
            increase[i]=INF;
            pre[i]=0;
            vis[i]=false;
        }
        vis[s]=true;
        queue<int> q;
        q.push(s);
        dis[s]=0;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            vis[x]=false;
            for(int i=head[x];i;i=nxt[i]){
                int y=to[i];
                if(flow[i] && dis[y]>dis[x]+cost[i]){
                    dis[y]=dis[x]+cost[i];
                    pre[y]=i;
                    increase[y]=min(increase[x],flow[i]);
                    if(!vis[y]){
                        vis[y]=true;
                        q.push(y);
                    }
                }
            }
        }
        return dis[t]<INF;
    }
    void update(){
        int cur=t;
        while(cur!=s){
            int last=pre[cur];
            flow[last]-=increase[t];
            flow[last^1]+=increase[t];
            cur=to[last^1];
        }
        ans+=(increase[t]*dis[t]);
    }
    void clear(){
        for(int i=0;i<=max(t,tot);i++){
            head[i]=to[i]=nxt[i]=flow[i]=cost[i]=0;
        }
        tot=1;
        ans=0;
    }
}

inline int read(){
    char ch;int x=0;bool f=false;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=true;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    if(f) x=-x;
    return x;
}

int dist(int x1,int y1,int x2,int y2){
    int a=abs(x1-x2),b=abs(y1-y2);
    return a*a+b*b;
}

int calc(int x,int r){
    int dam=0;
    for(int i=1;i<=ct;i++){
        if(dist(tow[x].x,tow[x].y,road[i].x,road[i].y)<=(r*r)){
            dam+=tow[x].p;
        }
    }
    return dam-pw[r];
}

signed main(){
    cin>>tt;
    pw[0]=1;
    for(int i=1;i<=12;i++) pw[i]=pw[i-1]*3;
    pw[0]=0;
    while(tt--){
        n=read(),m=read(),k=read();
        s=0,t=k+14;
        for(int i=1;i<=n;i++){
            string ss;
            cin>>ss;
            ss=" "+ss;
            for(int j=1;j<=m;j++){
                if(ss[j]=='#'){
                    road[++ct].x=i,road[ct].y=j;
                }
            }
        }
        for(int i=1;i<=k;i++){
            cin>>tow[i].x>>tow[i].y>>tow[i].p;
        }
        for(int i=1;i<=k;i++){
            EK::add(s,i,1,0);
            EK::add(i,s,0,0);
        }
        EK::add(k+1,t,INF,0);//当时判了一下r=0
        EK::add(t,k+1,0,0);
        for(int j=2;j<=13;j++){
            EK::add(j+k,t,1,0);
            EK::add(t,j+k,0,0);
        }
        for(int i=1;i<=k;i++){
            EK::add(i,k+1,INF,-calc(i,0));
            EK::add(k+1,i,0,calc(i,0));
            for(int j=1;j<=12;j++){
                int kl=calc(i,j);
                if(kl>0){
                    EK::add(i,k+j+1,1,-kl);
                    EK::add(k+j+1,i,0,kl);
                }
            }
        }
        while(EK::spfa()) EK::update();
        cout<<((-1)*ans)<<"\n";
        ct=0;
        EK::clear();
    }
    return 0;
}