题目
题目描述
给定一个$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)$的边
输出格式
输出一个数，表示最小化的费用
样例
样例输入
1 | 2 1 |
样例输出
1 | 1 |
数据范围与提示
样例说明
最优的方案是花费$1$的费用将$a_2$变成$0$
数据范围
对于$30\%$的数据，$n\leqslant 20$
对于$100\%$的数据，$n\leqslant 1000,m\leqslant 50000$
题解
奇奇怪怪的建图、跑网络流方法……
对于原图中的每一个点，建$i$的出度个点，把这些点和终点连上流量为$b_i$的边，然后把这些个点按$a_i$的值从小到大排序
然后搞个差分，再在这些个点之间连上流量为inf的边
最后跑一个网络流就可以啦！
注意，DFS中的取地址符非常重要，去掉了之后会超时，虽然我也不知道为啥反正就是加了就过了，因为我平常些Dinic的时候也不加这个取地址符
附上代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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);
}