CF1717F Madoka and The First Session
题目描述
Oh no, on the first exam Madoka got this hard problem:
Given integer n n n and m m m pairs of integers ( v i , u i v_i, u_i vi,ui ). Also there is an array b 1 , b 2 , … , b n b_1, b_2, \ldots, b_n b1,b2,…,bn , initially filled with zeros.
Then for each index i i i , where 1 ≤ i ≤ m 1 \leq i \leq m 1≤i≤m , perform either b v i : = b v i − 1 b_{v_i} := b_{v_i} - 1 bvi:=bvi−1 and b u i : = b u i + 1 b_{u_i} := b_{u_i} + 1 bui:=bui+1 , or b v i : = b v i + 1 b_{v_i} := b_{v_i} + 1 bvi:=bvi+1 and b u i : = b u i − 1 b_{u_i} := b_{u_i} - 1 bui:=bui−1 . Note that exactly one of these operations should be performed for every $ i $ .
Also there is an array s s s of length n n n consisting of 0 0 0 and 1 1 1 . And there is an array a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an , where it is guaranteed, that if s i = 0 s_i = 0 si=0 holds, then a i = 0 a_i = 0 ai=0 .
Help Madoka and determine whenever it is possible to perform operations in such way that for every i i i , where s i = 1 s_i = 1 si=1 it holds that a i = b i a_i = b_i ai=bi . If it possible you should also provide Madoka with a way to perform operations.
题面翻译
给出整数 n n n 和 m m m 对整数 ( v i , u i ) (v_i,u_i) (vi,ui)。同时有一个序列 B B B ,长度为 n n n ,保证一开始全为 0 0 0 。
然后对于每一对 ( v i , u i ) (v_i,u_i) (vi,ui),可以执行两种操作中的一种:
- b v i ← b v i − 1 , b u i ← b u i + 1 b_{v_i}\gets b_{v_i}-1,b_{u_i}\gets b_{u_i}+1 bvi←bvi−1,bui←bui+1
- b v i ← b v i + 1 , b u i ← b u i − 1 b_{v_i}\gets b_{v_i}+1,b_{u_i}\gets b_{u_i}-1 bvi←bvi+1,bui←bui−1
然后还会给你两个序列 A A A, S S S 长度均为 n n n,保证当 s i = 0 s_i=0 si=0 时, a i = 0 a_i=0 ai=0 。
问你在在所有操作方案中,是否有一种可以使得对于任意的 s i = 1 s_i=1 si=1,都有 a i = b i a_i=b_i ai=bi。
题解
这是一个网络流。
这里介绍一种巧妙的建图方法。
放个样例
5 5
1 1 1 1 1
-2 0 2 1 -1
1 5
1 4
3 5
3 4
4 5
首先建一个源点 S S S,一个汇点 T T T, X X X 部和 Y Y Y 部, X X X 部为数对 ( u , v ) (u,v) (u,v), Y Y Y 部为数 i i i,这时都把他们看作是点。把数对 ( u , v ) (u,v) (u,v) 分别连向 u , v u,v u,v,容量为 1 1 1; S S S 连向它,容量为 1 1 1。 i i i 连向 T T T,容量后面再说是多少。
按照样例,建出来的图长这样:( X X X 部(左边一列)的点代表的是数对 ( u , v ) (u,v) (u,v), Y Y Y 部(右边一列)的点代表数 i i i,这里右边一列的点的编号都加了 m m m)
在这个图上跑最大流。
假设一个大小为 1 1 1 的流量流到 X X X 部的某个点 i i i,这时它有两个选择,流向 u u u 或流向 v v v。不管流去哪里,另一个点的 b b b 值肯定要减一。加一在网络流的体现就是流量,但是减一呢?它并没有明显的表现。这样建图是正确的吗?
这就是它的巧妙之处。把有流量流过的边看作加一,没有流量流过的边看作减一,这样就解释得通了。
现在确定 Y Y Y 部与 T T T 之间边的容量。对于一个在 Y Y Y 部的点 i i i,记它的入度为 r i r_i ri,设有 x x x 个单位流量流经 i i i。
分类讨论一下,如果 s i = 0 s_i=0 si=0 容量就是无穷大,因为这个数没有限制。
下面是 s i = 1 s_i=1 si=1 的情况。
由流守恒,可知 x x x 就是我们想求的容量。
代表加一的流量为 x x x,所以代表减一的“流量”为 r i − x r_i-x ri−x。二者抵消,得 2 x − r i 2x-r_i 2x−ri,它应该等于 a i a_i ai。算出 x = r i + a i 2 x=\dfrac{r_i+a_i}{2} x=2ri+ai。
这样,图就建好了。如果无解,可能是 r i + a i r_i+a_i ri+ai 为奇数,或最大流不为 m m m,或 Y Y Y 部与 T T T 之间的边不满流。
一些细节
做最大流时,有可能流量都走某条无限边,导致原本是“Yes”,结果输出“No”。
我们可以先不建无限边,跑一遍网络流,再把无限边建上,再跑一遍网络流。这样就不会有问题了。
这道题还要求输出方案。 X X X 部有一点 i i i,它连向 u , v u,v u,v。若边 ( i , u ) (i,u) (i,u) 满流,就说明 u + + , v − − u++,v-- u++,v−−,反之同理。
数组开大点。每次做网络流前要清零。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e4+1,M=2e5+1;
const ll INF=1e18;
int n,d[N],vd[N],m,s,t,rd[N],a[N],b[N],aa[N],u[N],v[N];
int head[N],nxt[M],to[M],cnt=1;
ll w[M];
void add(int u,int v,ll W)
{
to[++cnt]=v;
w[cnt]=W;
nxt[cnt]=head[u];
head[u]=cnt;
}
ll aug(int i,ll augco,int n)
{
if(i==t) return augco;
ll augc=augco;
int mind=n-1;
for(int j=head[i];j;j=nxt[j]){
if(w[j]>0){
if(d[i]==d[to[j]]+1){
ll delta=aug(to[j],min(augc,w[j]),n);
w[j]-=delta,w[j^1]+=delta;
augc-=delta;
if(d[s]>n) return augco-augc;
if(!augc) break;
}
mind=min(mind,d[to[j]]);
}
}
if(augco==augc){
vd[d[i]]--;
if(!vd[d[i]]) d[s]=n;
d[i]=mind+1;
vd[d[i]]++;
}
return augco-augc;
}
ll sap(int n)
{
ll ans=0;
memset(vd,0,sizeof(vd));
memset(d,0,sizeof(d));
vd[0]=n;
while(d[s]<n) ans+=aug(s,INF,n);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
s=n+m+1,t=n+m+2;
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) add(s,i,1),add(i,s,0),rd[i]++;
for(int i=1;i<=m;i++){
scanf("%d%d",&u[i],&v[i]);
add(i,u[i]+m,1),add(u[i]+m,i,0),rd[u[i]+m]++;
add(i,v[i]+m,1),add(v[i]+m,i,0),rd[v[i]+m]++;
}
for(int i=1;i<=n;i++){
if(b[i]){
if((a[i]+rd[i+m])%2) puts("No"),exit(0);
else add(i+m,t,(a[i]+rd[i+m])/2),add(t,i+m,(a[i]+rd[i+m])/2),aa[i]=cnt-1;
}
}
ll ans=sap(t);
for(int i=1;i<=n;i++) if(!b[i]) add(i+m,t,INF),add(t,i+m,0);
ans+=sap(t);
if(ans!=m) puts("No"),exit(0);
for(int i=1;i<=n;i++) if(b[i]) if(w[aa[i]]) puts("No"),exit(0);
puts("Yes");
for(int i=1;i<=m;i++){
if(!w[2*m+2+i*4-3]) printf("%d %d\n",u[i],v[i]);
else printf("%d %d\n",v[i],u[i]);
}
}
文章来自于网络,如果侵犯了您的权益,请联系站长删除!