Problem - F - Codeforces
818 Div 2.F. Madoka and The First Session
思路：
不妨转化一下题意：
将条件转化为：\(b_v+1,b_v+1\),然后使得其中一个-2
那么在\(a\)上就是使\(a_v-1,a_u-1\),然后使得其中一个+2
问能否使得\(a\)数组全部为0（仅仅只对于每个\(s_i\)为1）（因为这是倒推，相当于从\(a\)得到\(b\)）
（由于当\(s_i\)为0时，其\(a_i\)不一定为准确值，那么倒推的值不一定为0）
我们可以先全部减完，那么无解的条件便是：对于每一个\(s_i\)为1时，存在\(a_i\)为奇数或\(a_i>0\)
显然，减完1之后我们只能加2，若a为奇数或大于0则必然不可能使得其变成0
于是乎，我们的问题就变成了如何安排+2
我们是知道每个数需要加多少次的，不妨构造网络流，A集合（及左部）为边，B集合（即右部）为点。这样构造有什么好处？
原因在于每一条边+2的权利都只能用一次，我们从源点连向A集合每一个点，并使其容量为1便可以做到；
对于每一条边，我们会连接两个点，于是从A集合连向B集合，容量也为1，相当于是每个A部分的点都会连接两个B部分的点
对于B部分的点，分情况讨论：
若此点的\(s_i\)为1，那么就让其连向t，容量为其需要的次数
若此点的\(s_i\)为0，那么就让其连向\(mid\)，\(mid\)为一个中介节点，目的是让其流量守恒，容量为无限大（反正它也没有限制）
最后，让\(mid\)连向\(t\)，满足守恒之后，若满流则有解，直接输出答案即可；否则输出NO
时间复杂度：
边数:\(4m+1\)(大概) 点数：\(n+m\)
\(dinic\)在二分图上极为优秀，其时间复杂度为\(O(m\sqrt{n})\),足以通过此题
//
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int INF=0x3f3f3f3f;
int n,m,s,t,mid;
int S[maxn],A[maxn];
int l[maxn],r[maxn];
struct node{
int data,nxt,val;
}a[maxn];
int first[maxn];
int cnt=1;
int d[maxn],vis[maxn];
queue<int>q;
void add(int x,int y,int val){
a[++cnt].data=y;
a[cnt].val=val;
a[cnt].nxt=first[x];
first[x]=cnt;
a[++cnt].data=x;
a[cnt].val=0;
a[cnt].nxt=first[y];
first[y]=cnt;
}
int bfs(){
memset(d,0,sizeof(d));
while(q.size())q.pop();
q.push(s);d[s]=1;;
while(q.size()){
int x=q.front();
q.pop();
for(int i=first[x];i!=0;i=a[i].nxt){
int k=a[i].data;
if(a[i].val&&!d[k]){
q.push(k);
d[k]=d[x]+1;
if(k==t)return 1;
}
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t)return flow;
int r=flow,k,i;
for(i=first[x];i&&r;i=a[i].nxt){
if(a[i].val&&d[a[i].data]==d[x]+1){
k=dinic(a[i].data,min(r,a[i].val));
if(!k)d[a[i].data]=0;
a[i].val-=k;
a[i^1].val+=k;
r-=k;
}
}
return flow-r;
}
int work(int x){
for(int i=first[x];i;i=a[i].nxt){
int k=a[i].data;
if(k==s)continue;
if(a[i^1].val){
return k-m;
}
}
return 114514;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&S[i]);
for(int i=1;i<=n;i++)scanf("%d",&A[i]);
for(int i=1;i<=m;i++){
scanf("%d%d",&l[i],&r[i]);
A[l[i]]--,A[r[i]]--;
}
for(int i=1;i<=n;i++){
if((S[i]&&(A[i]&1))||A[i]>0){
printf("NO\n");
return 0;
}
}
t=m+n+2;mid=n+m+1;
for(int i=1;i<=m;i++)add(s,i,1);
for(int i=1;i<=m;i++){
add(i,l[i]+m,1);
add(i,r[i]+m,1);
}
int v=0;
for(int i=1;i<=n;i++){
if(S[i]==1)add(i+m,t,-A[i]/2),v=v+(-A[i]/2);
else add(i+m,mid,INF);
}
if(m-v<0){
printf("NO\n");
return 0;
}
add(mid,t,m-v);
int ans=0;
while(bfs())ans+=dinic(s,INF);
if(ans!=m)printf("NO\n");
else{
printf("YES\n");
for(int i=1;i<=m;i++){
int x=work(i);
if(x==r[i])printf("%d %d\n",r[i],l[i]);
else printf("%d %d\n",l[i],r[i]);
}
}
return 0;
}