题解 P6061 【[加油武汉]疫情调查】

· · 题解

update1:感谢 @linfourxu 指出文章错误，已经更正。

update2:上次修改不完全，仍有残余错误。

给一个有向图，求用若干个环（或点）将整张图覆盖的最小花费。

求最小覆盖，想到带权二分图匹配问题，可以用费用流一波带走。

我们发现 n\leq 500 其实很小，足够我们跑一遍 Floyd 求出覆盖两个点的最小花费。然后我们将每一个点拆成两个点 (u,u') ，建立超级源超级汇 s,t 进行如下建模：

我们发现这张图一定存在完美匹配，那么就跑一遍最小费用最大流就可以拿到 70pts。

为什么会超时呢？因为跑一遍 Floyd 会使 m 达到 O(n^2)，显然无法承受。

我们考虑减少边的数量，由于最短路是由若干条路径拼成的，我们可以只在网络流建模中连接数据给出的边，同时从 u' 向 u 连一条流量为 \inf，费用为 0 的边（这应该是标准套路了）。这样我们可以顺着这些边走出一条最短路径，而且边的数量减少到 O(m+n)，可以通过本题。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int unsigned long long
struct edge
{
    int nxt,to,weight,value;
}e[1000001<<1];
int n,m,tot=1,h[10005],dep[10005],cur[10005],s,t,a[5001],cost,ans,hg[10005];
bool vis[10005];
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void add(int x,int y,int w,int val)
{
    e[++tot].nxt=h[x];
    h[x]=tot;
    e[tot].to=y;
    e[tot].weight=w;
    e[tot].value=val;
}
inline bool Dijkstra()
{
    for(register int i=0;i<=t;++i)
    {
        vis[i]=0;
        dep[i]=0x3f3f3f3f;
        cur[i]=h[i];
    }
    __gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int> >,pairing_heap_tag> q;
    q.push(make_pair(0,t));
    dep[t]=0;
    while(!q.empty())
    {
        pair<int,int> k=q.top();
        q.pop();
        if(vis[k.second])
            continue;
        vis[k.second]=1;
        for(register int i=h[k.second];i;i=e[i].nxt)
            if(e[i^1].weight&&dep[e[i].to]>dep[k.second]-e[i].value+hg[k.second]-hg[e[i].to])
            {
                dep[e[i].to]=dep[k.second]-e[i].value+hg[k.second]-hg[e[i].to];
                q.push(make_pair(dep[e[i].to],e[i].to));
            }
    }
    return dep[0]!=dep[s];
}
int dfs(int k,int f)
{
    int r=0;
    if(!f||k==t)
    {
        vis[t]=1;
        ans+=f;
        return f;
    }
    int used=0;
    vis[k]=1;
    for(register int i=cur[k];i;i=e[i].nxt)
    {
        cur[k]=i;
        if((!vis[e[i].to]||e[i].to==t)&&dep[e[i].to]==dep[k]-e[i].value+hg[k]-hg[e[i].to]&&e[i].weight)
            if((r=dfs(e[i].to,min(f-used,e[i].weight))))
            {
                cost+=e[i].value*r;
                e[i].weight-=r;
                e[i^1].weight+=r;
                used+=r;
                if(f==used)
                {
                    //vis[k]=0;
                    break;
                }
            }
    }
    return used;
}
inline int dinic()
{
    while(Dijkstra())
    {
        vis[t]=1;
        while(vis[t])
        {
            memset(vis,0,sizeof(vis));
            dfs(s,1<<20);
        }
        memset(vis,0,sizeof(vis));
        for(register int i=0;i<=t;++i)
            hg[i]+=dep[i];
    }
    return cost;
}
signed main()
{
    n=read(),m=read();
    s=n<<1|1;
    t=s+1;
    for(register int i=1;i<=n;++i)
    {
        a[i]=read();
        add(s,i,1,0);
        add(i,s,0,0);
        add(i+n,t,1,0);
        add(t,i+n,0,0);
        add(i,i+n,1<<20,a[i]);
        add(i+n,i,0,-a[i]);
        add(i+n,i,1<<20,0);
        add(i,i+n,0,0);
    }
    for(register int i=1;i<=m;++i)
    {
        int x=read(),y=read(),w=read();
        add(x,y+n,1<<20,w);
        add(y+n,x,0,-w);
    }
    printf("%lld\n",dinic());
    return 0;
}