F. Madoka and The First Session
/*
首先是对权值进行处理,把每次操作都看成一个减去2就可以了
这样就只需要对大家都减去一个1,最后如果有奇数或者大于0,那就一定不可以
然后就是见图,对边进行建图,代表这条边只能跑一次
对si=1的直接建立边就可以了
si=0的需要建立中转点,因为要限制流量
最后输出,反过来看边这么选择的点就可以了
*/
#include <bits/stdc++.h>
using namespace std;
const int N=2e4+10,M=1e5+5;
const int inf=1e9;
int h[N],ne[M],e[M],w[M],tot=1;
void add(int a,int b,int c) {
e[++tot]=b; w[tot]=c; ne[tot]=h[a]; h[a]=tot;
e[++tot]=a; w[tot]=0; ne[tot]=h[b]; h[b]=tot;
}
int n,m,S=N-2,T=N-1;
int dep[N],cur[N];
bool bfs() {
memset(dep,0,sizeof(dep));
memcpy(cur,h,sizeof(h));
// cout<<cur[S]<<endl;
queue<int>q;
q.push(S);dep[S]=1;
while(!q.empty()) {
int now=q.front();q.pop();
for(int i=h[now];i;i=ne[i]) {
int to=e[i];
if(dep[to]==0&&w[i]>0)
dep[to]=dep[now]+1,q.push(to);
}
}
return dep[T];
}
int dfs(int now,int sum) {
if(now==T)return sum;
int ans=0;
// cout<<cur[now]<<endl;
// cout<<h[now]<<endl;
for(int i=cur[now];i&∑i=ne[i]) {
cur[now]=i;
int to=e[i];
// cout<<to<<endl;
if(dep[to]==dep[now]+1&&w[i]>0) {
int k=dfs(to,min(w[i],sum));
if(k==0)dep[to]=-1;
ans+=k,sum-=k;
w[i]-=k,w[i^1]+=k;
}
}
return ans;
}
int dinic() {
int ans=0;
while(bfs())ans+=dfs(S,inf);
return ans;
}
int s[N],a[N];
int p[N][2];
void solve() {
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++) {
cin>>p[i][0]>>p[i][1];
a[p[i][0]]--,a[p[i][1]]--;
}
for(int i=1;i<=n;i++)
if(s[i]&&(a[i]%2||a[i]>0)) {
cout<<"NO\n";
return ;
}
for(int i=1;i<=m;i++) {
add(S,i,1);
add(i,p[i][0]+m,1);
add(i,p[i][1]+m,1);
}
int sum=0,tmp=N-3;
for(int i=1;i<=n;i++) {
if(s[i]) {
add(m+i,T,-a[i]/2);
sum-=a[i]/2;
}
else add(m+i,tmp,inf);
}
add(tmp,T,m-sum);
int ans=dinic();
//不能满足流量,或者是需求过大
if(ans!=m||sum>m)cout<<"NO\n";
else {
cout<<"YES\n";
for(int now=m+1;now<=n+m;now++) {
for(int i=h[now];i;i=ne[i]) {
int to=e[i];
if(to<=m&&w[i]) {
if(p[to][0]!=now-m)swap(p[to][0],p[to][1]);
}
}
}
for(int i=1;i<=m;i++)cout<<p[i][0]<<' '<<p[i][1]<<'\n';
}
}
signed main() {
solve();
return 0;
}
标签:Madoka,return,int,tot,dep,Session,ans,now,First
From: https://www.cnblogs.com/basicecho/p/17391908.html