题目

题目描述

给定一个$n$个点，$m$条边的有向图
对于任意一个点$i$，都有两个权值$a_i,b_i$
你可以花费$b_i$的费用将这个点的$a_i$变成$0$
另外对于圈中的每个点你需要付出$wi=Max(i,j)\in E~aj$
请最小化所有费用之和

输入格式

第一行两个数$n$，$m$
接下来一行$n$个数，表示$a_i$
接下来一行$n$个数，表示$b_i$
接下来$m$行，每行$2$个数$i,j$，表示一行$(i,j)$的边

输出格式

输出一个数，表示最小化的费用

样例

样例输入

2 1
100000 10000
100000 1
1 2

样例输出

数据范围与提示

样例说明

最优的方案是花费$1$的费用将$a_2$变成$0$

数据范围

对于$30%$的数据，$n\leqslant 20$
对于$100%$的数据，$n\leqslant 1000,m\leqslant 50000$

题解

奇奇怪怪的建图、跑网络流方法……
对于原图中的每一个点，建$i$的出度个点，把这些点和终点连上流量为$b_i$的边，然后把这些个点按$a_i$的值从小到大排序
然后搞个差分，再在这些个点之间连上流量为inf的边
最后跑一个网络流就可以啦！
注意，DFS中的取地址符非常重要，去掉了之后会超时，虽然我也不知道为啥~~反正就是加了就过了~~，因为我平常些Dinic的时候也不加这个取地址符
附上代码：

#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct ppap1
{
    int v,h;
}temp[200010];
struct ppap2
{
    int to,nxt,ver;
}e[400010];
vector<int> t[200010];
queue<int> q;
int n,m,S,T,tot=1,len,ans,a[1010],b[1010],u[50010],v[50010],head[200010],Head[200010],d[200010],vis[200010];
inline int read()
{
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
}
inline bool cmp(ppap1 a,ppap1 b)
{
    return a.v<b.v;
}
inline void add(int u,int v,int w)
{
    e[++tot].nxt=head[u],head[u]=tot,e[tot].to=v,e[tot].ver=w;
    e[++tot].nxt=head[v],head[v]=tot,e[tot].to=u,e[tot].ver=0;
}
inline bool bfs()
{
    for(int i=1;i<=T;i++) d[i]=1e9;
    d[S]=0,q.push(S);
    while(!q.empty()){
        int x=q.front();
        q.pop(),Head[x]=head[x];
        for(int i=head[x];i;i=e[i].nxt) if(d[e[i].to]>d[x]+1&&e[i].ver>0){
            d[e[i].to]=d[x]+1;
            if(!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to);
        }
        vis[x]=0;
    }
    return d[T]!=1e9;
}
inline int dfs(int x,int Flow)
{
    if(x==T||(!Flow)) return Flow;
    int k,flow=0;
    for(int &i=Head[x];i;i=e[i].nxt) if(d[e[i].to]==d[x]+1&&(k=dfs(e[i].to,min(e[i].ver,Flow)))>0){
        e[i].ver-=k,e[i^1].ver+=k,Flow-=k,flow+=k;
        if(!Flow) break;
    }
    return flow;
}
int main()
{
    n=read(),m=read();
    S=200002,T=S+1,len=n;
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read(),add(i,T,b[i]);
    for(int i=1;i<=m;i++) u[i]=read(),v[i]=read(),t[u[i]].push_back(v[i]);
    for(int i=1,size;i<=n;i++){
        size=t[i].size();
        for(int j=0;j<size;j++) temp[j].h=t[i][j],temp[j].v=a[t[i][j]];
        sort(temp,temp+size,cmp);
        for(int j=0,tem;j<size;j++){
            tem=++len;
            if(!j) add(S,tem,temp[j].v);
            else add(S,tem,temp[j].v-temp[j-1].v),add(tem-1,tem,1e9);
            add(tem,temp[j].h,1e9);
        }
    }
    while(bfs()) ans+=dfs(S,1e9);
    printf("%d",ans);
}